Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Function of N of a Sort in Java
New Posts  All Forums:Forum Nav:

Function of N of a Sort in Java

post #1 of 11
Thread Starter 
Hello, I have been having a tough time figuring a function of n for a snippet of code. I honestly don't know how to tackle this particular problem.

Assuming 'n' is the length of the array, how often is the if statement executed?

public sortArray(int[] array) {
for (int i = 0; i < array.length; i++) {
int j = i;
while (j > 0) {
if (array[j] < array[j-1]) {
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
j--;
}
}
}


Doesn't the number of times the if statement runs vary based upon the values in the array? Wouldn't this be "random"?

If anyone could walk me through deriving the answer, it would be very helpful.
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
post #2 of 11
Quote:
Originally Posted by FusionFX View Post
Hello, I have been having a tough time figuring a function of n for a snippet of code. I honestly don't know how to tackle this particular problem.

Assuming 'n' is the length of the array, how often is the if statement executed?

public sortArray(int[] array) {
for (int i = 0; i < array.length; i++) {
int j = i;
while (j > 0) {
if (array[j] < array[j-1]) {
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
j--;
}
}
}


Doesn't the number of times the if statement runs vary based upon the values in the array? Wouldn't this be "random"?

If anyone could walk me through deriving the answer, it would be very helpful.
Yes it would definitly be random, as the data in the array is randomly sorted. However there may be some way to take an average or expected value, but idk what that would be.
Scream Machine
(9 items)
 
  
CPUMotherboardGraphicsRAM
i7-4770K Gigabyte Z87X-UD3H EVGA GTX 780 16GB DDR3 
Hard DriveCoolingOSMonitor
256GB Samsung 840 Pro Kraken X60 Windows 7 Shimian 2560x1440 
Case
Phantom 630 
  hide details  
Reply
Scream Machine
(9 items)
 
  
CPUMotherboardGraphicsRAM
i7-4770K Gigabyte Z87X-UD3H EVGA GTX 780 16GB DDR3 
Hard DriveCoolingOSMonitor
256GB Samsung 840 Pro Kraken X60 Windows 7 Shimian 2560x1440 
Case
Phantom 630 
  hide details  
Reply
post #3 of 11
It depends what function you are looking for. I imagine you are talking about algorithm efficiency? If so, you have best case, worst case, and average case scenarios you want to look for. Each case has an associated letter that I cannot remember, some easy googling will figure that out for you, but its O, {PHI} and {Omega}; It's called Big notation, such as Big-O, so on and so forth.

Best Case: The list is ordered, and the if statement is never executed, so you have constant efficiency, denoted as 1 in the notation if you look it up

Worst Case: The list is in reverse order. In this case the nth element will execute the if-statement n times, the n-1 element n-1 times, so you have...(n^2+n)/2 executions of the if statement if my memory serves me. This is probably the formula you're looking for if it's not the Big function. This function gives n^2 efficiency(not good btw), but it seems like you're just learning about sorts and efficiency.

Average Case: Usually a lot stickier than something I could just throw out there, but generally there are formulas for general sorts like these, again if my memory serves me this is bubble sort.

So really it depends on what you mean by "function". But really in conclusion calculating algorithm efficiency generally boils down to hand waving, but it is very important material.
Lappy 3001
(13 items)
 
  
CPUMotherboardGraphicsRAM
i3-560 @ 3.85 GHz ASRock H55M-LE PNY XLR8 GTX 460 4G Corsair XMS3 DDR3 @ 1600 MHz 
OSMonitorPowerCase
Windows 7 / Ubuntu Samsun SyncMaster 226bw 22" Corsair CX600 Cooler Master HAF 932 
  hide details  
Reply
Lappy 3001
(13 items)
 
  
CPUMotherboardGraphicsRAM
i3-560 @ 3.85 GHz ASRock H55M-LE PNY XLR8 GTX 460 4G Corsair XMS3 DDR3 @ 1600 MHz 
OSMonitorPowerCase
Windows 7 / Ubuntu Samsun SyncMaster 226bw 22" Corsair CX600 Cooler Master HAF 932 
  hide details  
Reply
post #4 of 11
Thread Starter 
Supposedly it should be exact. In terms of big O notation should not be used.

I believe a single function is supposed to represent the sort. Regardless of the order of the array or any best, worst, average case.

I am having trouble wrapping my head around this, but thanks for your help LetThereBeDwight.
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
post #5 of 11
It is not random. Nothing in that snippet terminates the loop if the array is sorted already. They aren't asking how many times the swap command inside of the if is executed, just how many times the if is evaluated, which is every time the inner loop is executed.

Just ignore the fact that it's a sorting algorithm. How many times is the inner loop of the following executed

Code:
        for(int i = 0; i < N; ++i){
                for(int j = i; j > 0; --j){
                        ;// It doesn't matter what happens here
                }       
        }
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
post #6 of 11
Thread Starter 
Quote:
Originally Posted by rabidgnome229 View Post
It is not random. Nothing in that snippet terminates the loop if the array is sorted already. They aren't asking how many times the swap command inside of the if is executed, just how many times the if is evaluated, which is every time the inner loop is executed.

Just ignore the fact that it's a sorting algorithm. How many times is the inner loop of the following executed

Code:
        for(int i = 0; i < N; ++i){
                for(int j = i; j > 0; --j){
                        ;// It doesn't matter what happens here
                }       
        }
I am having a hard time expressing it...
The inner loop is executed i*i times unless i is equal to zero.
The greatest value of i can be n-1.

As an example. n = 7.

When i is 1, the inner loop runs once.
When i is 2, the inner loop runs twice.
etc...

You add each time the inner loop runs and you have the total of times in which the inner loop has been executed.

If n was 7, then the inner loop would run 21 times.

I am having quite the brain fart at the moment.
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
post #7 of 11
n! i believe.
Project Chloe
(16 items)
 
  
CPUMotherboardGraphicsRAM
i5-2500k 4.4GHz 1.280v Fatal1ty Z68 Professional Gen3 MSI R6950 Twin Frozr III Corsair Vengence 8GB 1600MHz 
Hard DriveHard DriveOptical DriveOS
OCZ Vertex 4 Samsung Spinpoint F3 Asus 24X DVD Burner Windows 7 Ultimate 64bit 
MonitorMonitorKeyboardPower
ASUS VE228H ASUS VE228H Razor Blackwidow  Corsair 850HX 
CaseMouseMouse PadAudio
HAF X Logitech G500 Razer Goliathus Logitech G930 
  hide details  
Reply
Project Chloe
(16 items)
 
  
CPUMotherboardGraphicsRAM
i5-2500k 4.4GHz 1.280v Fatal1ty Z68 Professional Gen3 MSI R6950 Twin Frozr III Corsair Vengence 8GB 1600MHz 
Hard DriveHard DriveOptical DriveOS
OCZ Vertex 4 Samsung Spinpoint F3 Asus 24X DVD Burner Windows 7 Ultimate 64bit 
MonitorMonitorKeyboardPower
ASUS VE228H ASUS VE228H Razor Blackwidow  Corsair 850HX 
CaseMouseMouse PadAudio
HAF X Logitech G500 Razer Goliathus Logitech G930 
  hide details  
Reply
post #8 of 11
Quote:
Originally Posted by FusionFX View Post
I am having a hard time expressing it...
The inner loop is executed i*i times unless i is equal to zero.
The greatest value of i can be n-1.

As an example. n = 7.

When i is 1, the inner loop runs once.
When i is 2, the inner loop runs twice.
etc...

You add each time the inner loop runs and you have the total of times in which the inner loop has been executed.

If n was 7, then the inner loop would run 21 times.

I am having quite the brain fart at the moment.
You're almost there. Write out the full sum for 7, then do the same for 8, then see if you can use that pattern to make an equation that gives how many times the inner loop runs N instead of some particular number
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
post #9 of 11
Well if were talking about exact, the question is how many times the if statement is reached, not how many times it will be stepped into. So the answer is in my above post.
Lappy 3001
(13 items)
 
  
CPUMotherboardGraphicsRAM
i3-560 @ 3.85 GHz ASRock H55M-LE PNY XLR8 GTX 460 4G Corsair XMS3 DDR3 @ 1600 MHz 
OSMonitorPowerCase
Windows 7 / Ubuntu Samsun SyncMaster 226bw 22" Corsair CX600 Cooler Master HAF 932 
  hide details  
Reply
Lappy 3001
(13 items)
 
  
CPUMotherboardGraphicsRAM
i3-560 @ 3.85 GHz ASRock H55M-LE PNY XLR8 GTX 460 4G Corsair XMS3 DDR3 @ 1600 MHz 
OSMonitorPowerCase
Windows 7 / Ubuntu Samsun SyncMaster 226bw 22" Corsair CX600 Cooler Master HAF 932 
  hide details  
Reply
post #10 of 11
Thread Starter 
Quote:
Originally Posted by rabidgnome229 View Post
You're almost there. Write out the full sum for 7, then do the same for 8, then see if you can use that pattern to make an equation that gives how many times the inner loop runs N instead of some particular number
f(n) = (n²-n)/2
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
mITX
(10 items)
 
  
CPUMotherboardRAMHard Drive
Intel Core i7 6700K Gigabyte GA-Z170N-Gaming 5 Corsair Vengeance 16GB (8GB x 2) - 3200MHz Samsung 850 EVO - 250GB 
Hard DriveOptical DriveCoolingOS
Western Digital RAID0 - 1TB LITE-ON iHAS124 CORSAIR Hydro H100i Windows 10 Pro 
PowerCase
Rosewill Capstone 750 Corsair Obsidian 250D 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Function of N of a Sort in Java