Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Need help with java quicksort, not sorting properly
New Posts  All Forums:Forum Nav:

Need help with java quicksort, not sorting properly

post #1 of 3
Thread Starter 
Hey all. My teacher gave me homework to write a quicksort algorythm in java. I managed to figure it out with his tips, but it's still not working as intended. It just won't sort. And pardon the language, I'm from Poland tongue.gif Any help would be much appreciated. Here is the code:
Code:
public class Main {

        /**
         * @param args
         */
        public static void main(String[] args) {
                int tab[] = new int[6];
                tab[0] = 3;
                tab[1] = 1;
                tab[2] = 74;
                tab[3] = 15;
                tab[4] = 26;
                tab[5] = 52;

                Quicksort tablica = new Quicksort(tab);
                tablica.wyswietl(tab);
        }

}
Code:
public class Quicksort {
        
        int[] liczby;

        public Quicksort(int tab[]){
                liczby = tab;
                sortuj(0, tab.length-1);
        }
        
        public void wyswietl(int tab[]){
                for (int i=0; i<tab.length; i++){
                        System.out.print(tab[i] + " ");
                }
        }
                
        public void zamienLiczby(int a, int b){
                int temp = liczby[a];
                liczby[a] = liczby[b];
                liczby[b] = temp;
        }

        public void sortuj(int left, int right){
                int m = (left+(right-left))/2;
                int i = left;
                int j = right;
                
                while (i<=j){
                        while (liczby[i]<liczby[m]){
                                i++;
                        }
                        while (liczby[j]>liczby[m]){
                                j--;
                        }
                        if (i<=j){
                                zamienLiczby(i,j);
                                i++;
                                j--;
                        }       
                }
                if (left < j){
                        sortuj(left,j);
                }
                if (right > i){
                        sortuj(right,i);
                }
        }
        
}
post #2 of 3
your quicksort algorithm looks pretty much correct. your biggest problem is in these lines:
Code:
1: Quicksort tablica = new Quicksort(tab);
2: tablica.wyswietl(tab);

the first line passes the scrambled array 'tab' to the Quicksort class, where it is sorted locally.
the second line passes the still scrambled array 'tab' to a method that prints the scrambled array. the problem is that 'tab' is never updated with the sorted array.

try doing something like this
Code:
public Quicksort(int tab[]){
                liczby = tab;
                sortuj(0, tab.length-1);
                wyswietl(liczby);
}

i didn't look at your quicksort algorithm in detail, so here is a good reference if you are still having problems with it. http://www.mycstutorials.com/articles/sorting/quicksort

good luck thumb.gif
Fractal Design
(15 items)
 
775 4 life
(15 items)
 
 
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix 
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64 
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W 
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer 
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400 
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi 
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5 
Mouse
Razor Abyssus 
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3 
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ... 
Power
9-cell plus Slice battery 
  hide details  
Reply
Fractal Design
(15 items)
 
775 4 life
(15 items)
 
 
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix 
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64 
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W 
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer 
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400 
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi 
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5 
Mouse
Razor Abyssus 
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3 
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ... 
Power
9-cell plus Slice battery 
  hide details  
Reply
post #3 of 3
Thread Starter 
The constructor of the Quicksort class already sorts these numbers. But I figured out what was wrong. I wrote
if (right > i){
sortuj(right,i);
}

insead of
if (right > i){
sortuj(i,right);
}


As usual it's just a minor mistake that makes your entire algorythm work like crazy xD Thanks for the help smile.gif
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Application Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Need help with java quicksort, not sorting properly