quicksort java

Solutions on MaxInterview for quicksort java by the best coders in the world

showing results for - "quicksort java"
Fynn
03 Apr 2018
1import java.util.Arrays;
2public class QuickSortInJava
3{
4   int partition(int[] arrNumbers, int low, int high)
5   {
6      int pivot = arrNumbers[high];
7      // smaller element index
8      int a = (low - 1);
9      for(int b = low; b < high; b++)
10      {
11         // if current element is smaller than the pivot
12         if(arrNumbers[b] < pivot)
13         {
14            a++;
15            // swap arrNumbers[a] and arrNumbers[b]
16            int temp = arrNumbers[a];
17            arrNumbers[a] = arrNumbers[b];
18            arrNumbers[b] = temp;
19         }
20      }
21      // swap arrNumbers[a + 1] and arrNumbers[high] or pivot
22      int temp = arrNumbers[a + 1];
23      arrNumbers[a + 1] = arrNumbers[high];
24      arrNumbers[high] = temp;
25      return a + 1;
26   }
27   void sort(int[] arrNumbers, int low, int high)
28   {
29      if (low < high)
30      {
31         int p = partition(arrNumbers, low, high);
32         /* recursive sort elements before
33         partition and after partition */
34         sort(arrNumbers, low, p - 1);
35         sort(arrNumbers, p + 1, high);
36      }
37   }
38   static void displayArray(int[] arrNumbers)
39   {
40      int s = arrNumbers.length;
41      for(int a = 0; a < s; ++a)
42         System.out.print(arrNumbers[a] + " ");
43      System.out.println();
44   }
45   public static void main(String[] args)
46   {
47      int[] arrNumbers = {59, 74, 85, 67, 56, 29, 68, 34};
48      int s = arrNumbers.length;
49      QuickSortInJava obj = new QuickSortInJava();
50      obj.sort(arrNumbers, 0, s - 1);
51      System.out.println("After sorting array: ");
52      displayArray(arrNumbers);
53   }
54}
Niclas
13 Jan 2020
1//GOD's quicksort
2public static <E extends Comparable<E>> List<E> sort(List<E> col) {
3  if (col == null || col.isEmpty())
4    return Collections.emptyList();
5  else {
6    E pivot = col.get(0);
7    Map<Integer, List<E>> grouped = col.stream()
8      .collect(Collectors.groupingBy(pivot::compareTo));
9    return Stream.of(sort(grouped.get(1)), grouped.get(0), sort(grouped.get(-1)))
10      .flatMap(Collection::stream).collect(Collectors.toList());
11  }
12}
Cordelia
24 Apr 2016
1
2import java.util.*;
3class QuickSort {
4    //selects last element as pivot, pi using which array is partitioned.
5    int partition(int intArray[], int low, int high) {
6        int pi = intArray[high];
7        int i = (low-1); // smaller element index
8        for (int j=low; j<high; j++) {
9            // check if current element is less than or equal to pi
10            if (intArray[j] <= pi) {
11                i++;
12                // swap intArray[i] and intArray[j]
13                int temp = intArray[i];
14                intArray[i] = intArray[j];
15                intArray[j] = temp;
16            }
17        }
18
19        // swap intArray[i+1] and intArray[high] (or pi)
20        int temp = intArray[i+1];
21        intArray[i+1] = intArray[high];
22        intArray[high] = temp;
23
24        return i+1;
25    }
26
27
28    //routine to sort the array partitions recursively
29    void quick_sort(int intArray[], int low, int high) {
30        if (low < high) {
31            //partition the array around pi=>partitioning index and return pi
32            int pi = partition(intArray, low, high);
33
34            // sort each partition recursively
35            quick_sort(intArray, low, pi-1);
36            quick_sort(intArray, pi+1, high);
37        }
38    }
39}
40
41class QUICK_SORT{
42    public static void main(String args[]) {
43        //initialize a numeric array, intArray
44        int intArray[] = {3,2,1,6,5,4};
45        int n = intArray.length;
46        //print the original array
47        System.out.println("Original Array: " + Arrays.toString(intArray));
48        //call quick_sort routine using QuickSort object
49        QuickSort obj = new QuickSort();
50        obj.quick_sort(intArray, 0, n-1);
51        //print the sorted array
52        System.out.println("\nSorted Array: " + Arrays.toString(intArray));
53    }
54}
Khalil
04 Mar 2017
1	//Worst case: if pivot was at the end and all numbers are greater than the pivot
2	//Best case: (n log n): due to you cutting the array in half n times
3	// Average case(n log n): ^
4
5public class QuickSort {
6	
7	public static void main(String [] args) {
8		int [] arr = {5, 1, 6, 4, 2, 3};
9		quickSort(arr, 0, arr.length);
10		
11      	/*Using a for each loop to print out the ordered numbers from the array*/
12      	for(int i: arr){
13        	System.out.println(i);
14        }// End of the for-each loop
15	
16	}// End of the main method
17	
18	public static void quickSort(int [] arr, int start, int end) {
19		/*Base case*/
20		if(start >= end) {
21			return;
22		}// End of the base case
23		
24		int pIndex = partition(arr, start, end);// The index of the pivot.
25		//System.out.println(pIndex);
26		
27		/*Recursive cases*/
28		quickSort(arr, start, pIndex - 1);// Left side of the array
29		quickSort(arr, pIndex + 1, end);// Right side of the array
30		
31	}// End of the quicksort method
32	
33	public static int partition(int [] arr, int start, int end) {
34		int pivot = arr[end - 1];// Select the pivot to be the last element
35		int pIndex = start;// (Partition index) Indicates where the pivot will be. 
36		
37		for(int i = start; i < end; i++) {
38			if(arr[i] < pivot) {
39				
40				// if a number is smaller than the pivot, it gets swapped with the Partition index
41				int temp = arr[pIndex];
42				arr[pIndex] = arr[i];
43				arr[i] = temp;
44				
45				pIndex++;// increments the partition index, only stops when pivot is in the right area
46			}// End of the if statement
47			
48		}// End of the for loop
49		
50		// This swaps the pivot with the element that stopped where the pivot should be
51		arr[end - 1] = arr[pIndex];
52		arr[pIndex] = pivot;
53		return pIndex;
54	}// End of the partition method
55	
56}// End of the QuickSort class
Santiago
26 Jan 2020
1// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
2// @see https://www.youtube.com/watch?v=aXXWXz5rF64
3// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
4
5function partition(list, start, end) {
6    const pivot = list[end];
7    let i = start;
8    for (let j = start; j < end; j += 1) {
9        if (list[j] <= pivot) {
10            [list[j], list[i]] = [list[i], list[j]];
11            i++;
12        }
13    }
14    [list[i], list[end]] = [list[end], list[i]];
15    return i;
16}
17
18function quicksort(list, start = 0, end = undefined) {
19    if (end === undefined) {
20        end = list.length - 1;
21    }
22    if (start < end) {
23        const p = partition(list, start, end);
24        quicksort(list, start, p - 1);
25        quicksort(list, p + 1, end);
26    }
27    return list;
28}
29
30quicksort([5, 4, 2, 6, 10, 8, 7, 1, 0]);
31
Amanda
22 Feb 2020
1public static ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list)
2{
3    if (list.isEmpty()) 
4        return list; // start with recursion base case
5    ArrayList<Vehicle> sorted;  // this shall be the sorted list to return, no needd to initialise
6    ArrayList<Vehicle> smaller = new ArrayList<Vehicle>(); // Vehicles smaller than pivot
7    ArrayList<Vehicle> greater = new ArrayList<Vehicle>(); // Vehicles greater than pivot
8    Vehicle pivot = list.get(0);  // first Vehicle in list, used as pivot
9    int i;
10    Vehicle j;     // Variable used for Vehicles in the loop
11    for (i=1;i<list.size();i++)
12    {
13        j=list.get(i);
14        if (j.compareTo(pivot)<0)   // make sure Vehicle has proper compareTo method 
15            smaller.add(j);
16        else
17            greater.add(j);
18    }
19    smaller=quickSort(smaller);  // capitalise 's'
20    greater=quickSort(greater);  // sort both halfs recursively
21    smaller.add(pivot);          // add initial pivot to the end of the (now sorted) smaller Vehicles
22    smaller.addAll(greater);     // add the (now sorted) greater Vehicles to the smaller ones (now smaller is essentially your sorted list)
23    sorted = smaller;            // assign it to sorted; one could just as well do: return smaller
24
25    return sorted;
26}
queries leading to this page
quicksort average case space usedthe quicksort algorithm can be used toproperties of quicksortjava quick sort methodquick sort c nao faz pra posicao do meioalgorithm time complexity quick sortwrite a program to implement quick sort algorithm in javapivot element in quick sortwhat is the big o of quicksorthow to implement quick sort in javaquicksort 28 29 javaquick sort best casequicksort average casequicksort space and time complexityaverage case complexity of quick sortquick sort time complexity best casejava quicksort algorithmquicksort algorithm by lengthquicksort conceptquick sort basic code javaquick sort explanation in javaquicksort java ytquicksort java 8simplest definition of quicksortquick sort correct java implementationquick sort worst case big o notationquick sort best time complexityquicksort java easy shortquicksort mediaaverage time quicksortquick sort program javaquick sort for javahow to quick sort with javaquickenquicksort java codebinary search and quick sort are both examples of what sort of algorithm 3fin place quicksort javaquick sort algorithm is in javaquicksort workingquicksort time complexity of quick sort in worst caseworst case time complexity of quicksort in placequick sortalgorithm in javaquicksort alofounder of quicksortpartition sort length nsimple quicksort javain place quicksortjava util quicksortthree way quicksort java codebest case time complexity of quicksorthow to quicksort array in javaworst case time complexity quick sortquick sort algrotihm javaquick sort definitionquicksort tutorialhow does a quicksort workquicksort javaquicksort bigoexplain quick sort worst case time complexity of the quick sort algorithmquicksort concept javaquicksort programhow to quick sort javaquicksort java time complexityjava official quicksort algorithmjava quickstortjava implement quick sortquicksort to sort an array in javapartition sortsorting quicksortwhat is the average time complexity of quicksort 3fjava quicksort implementationspace complexity of quicik sortquick sorting algorithm javajava quicksort examplequick sort time complexquick sort in java simple programpartition sort length quicksort for javajava array sort quicksortquicksortvariation of quicksort 3aquicksort algorithm arraylist javaquick sort method java quick sort averagequicksandquick sorting javathe average case complexity of quick sort for sorting n numbers isquick sort worst case time complexityquick sort library in javabest case time complexity quick sortquick sort time complexity worst casetime complexity of quicksort in worst casequick sort in algorithmquicksort sort codequick sort explain javatime complexity for quick sortjava quicksort 2 pointerquick sort big oquick sort ascending order javanew quicksort 28 29java program to implement the quicksort algorithmquicksort sortplace and divide quick sort pivot in the middleaverage complexity of quicksortquick sort java how it worksquicksort time complexityquicksort function javahow does the quicksort algorithm workwhat is the worst case complexity of quicksort o 28n2 29 3fsort quicksortquicksort definitioneasy quicksortjava quicksort with list arrayquicksort code in javaquicksort correct java implementationarraylist quicksortquick sort in java programquicksort highquicksort worst case time complexitywhy use the quick sort can optimal scheduleb quicksort half partitionquicksort examplequicksort partition algorithm javaworst case time complexity of quick sortquicksort big o classjava what is quicksortquick sorting in javapartition in quicksort time complexityquicksort java in list if list is an objectsimple quick sort javaaverage case analysis of quicksortwhat is the worst case and best case runtime of quick sort for sorting n number of datasimple quicksortquick sort java programquick sort using arraylist in javaquicksort implementation javajava quicksort simplebest case running time for quicksortexplain quicksortsort array using quicksort in javaquicksort complexitybest algorithm quicksort in javaquicksort java algorithmquick sort array algorithm javaquik sort in javaquick sort implementation java3 way quicksort javajava quicksort arraylistsorting an array using quicksort javaquickqortquicksort inoperating systemswhat is quicksort what is the time complexiry of quick sortrecurrence equal for worst case of quick sort 3fhow to program quick sort javaquicksort wikipediajava quick sort codequicksort algorithm runtimequick sort best case time complexityhow to do quick sort in javaexplain important properties of ideal sorting algorithm and complexity analysis of quick sort time complexity of quicksort algorithmtime complexity quicksortjava quick sort exampleplace and divide quicksort pivot in the middlequicksort algorithm quicksort arraylist javaquick sort average runtimebest time and worst time complexity for quick sort algorithmquicksort time complexity is based on pivothow quicksort worksquicksort hoarequicksort method in javapartition algorithm complexityquicksort program javaquicksort of an array javajava quicksort ascending orderquick sort in javaquicksort explanation time complexity of quick sort in worst and best case using master theorem java quicksort code easyhow the quicksort workquicksortr space complexityquick sort for an array javajava quicksortquick sort algortithm javaquicksort javquick sortquicksort algorithm java codequick sort code in javaquick sort java codejava quicksort codequicksort diagramquick sort program in javasorted fast 3fquick sort ni javarequirements for quick sortquicksort java arraylistque es quick sortworst time complexity of quick sortquick sort algorithmimplementing quick sort in javajava problem for quicksortaverage case of quicksortquick sort algorithm for arraylistquicksort program in javaquicksort in javaquick sort time complexir 3dty if sortedquicksort complexityquicksorts javaquicksort code3 way quicksort in javatime complexity of quick sortquicksort algorithm code javaquicksort time complexity best casequicksort engquick sort algorithm java with examplequick sort example javajava program to implement quick sort algorithmquicksort exhow does quicksort work javaquick sorting algorithms javaquick sort an arraylist of obkectsquick sort using javawrite short note on 3a a 29 discrete optimization problems b 29 parallel quick sortquick sort complextythree way quicksort javaquick sort code for javaquick sort javaquicksort for arraylistkquicksort 3ajava quicksort downquicksort space complexityquick sort best and worst case codecost quicksortquick sort in javaquicksort java c2 b4best and worst cases of quick sort with examplequick sort algorithm javaquick sort time complexityquicksort library in javaquicksort is aquicksort java programtime complexity of quice sortjava code for quick sortorder quicksortquicksort list with objects in javaquicksort java 5djava quicksort functionbest case complexity of quick sortquick sort algo javaquick sort algorithm code kavaaverage case time complexity of quicksortquicksort explained javawhen to use quicksortquicksort javaquick sortquick sort wikitime complexity of quicksortquick sort algorithm in javaspace complexity quick sortquick algorith javaquicksort in c bigohow use quicksort javatime complexity graph of quicksortin partition algorithm 2c the subarray has elements which are greater than pivot element x ways to implement quicksortquick sort code javathe average time complexity of quicksort is 3fquick sorting quicksort partitioningquicksort algorithmquicksort in place implementation javaquick sort execution timequicksort algorithm explainedquicksort analysisquicksort implement in javaquick sort javaquick sort javaexplanation of quick sort program in java quicksortquocksortquick sort arraylist 3ct 3e javaquick sort space complexityquicksort jvaquick sort algorithms javajava array sort quicksort implementationquick sort in placethe worst case time complexity of quick sort isjava quicksort arrayquicksort java explainedquicksort definationhow does quicksortquicksort algorithm explanationhow does quicksort work in javaquick sort code with javaquick sort algorithm 27using quicksort javaquicksort 28arraylist java 29quicksort algorithm timingjava quick sort code easywhat is best case worst case and average case for quick sortspace complexity of quick sortquick sort of an array javawhat is the best case time complexity of quick sortfunction for quick sort in javaspace complexity of quicksortquicksort algorithm javajava quicksort 28arraylist 29quicksort explainedaverage case time complexity of quick sortquicksort 5c analysiswhat is the worst case time complexity of a quick sort algorithm 3fjava quicksort recursionwrite a code using quick sort in javaquick sort big o average timequick sort use casequicksort code javahow to write a quicksort in javaquicksort implementation in javaquicksort java apisorting algorithm uses the value based partitionwhat is quick sort in javaquicksirt diagramsquicksort wikihow does quicksort workcomplexidade assimptomatica quick sortefficiency of quicksort algorithmwhen will quicksort workquick osrt in placespace complexity for quicksortquicksort c 23 wikiis quicksort algorithm 23define quicksortquick sort in java first element as pivotjava quick sort quicksort easy program javaquicksort functioneverything about quicksort in depthy quicksort can optimal the schdulewhen is quicksort usedhow to code quicksort javajava quicksorquicksort java implementationwho invented quicksorthoar quicksortquicksort algorithm codequicksort implementationjava quicksortquick sort in java programming simplifiedquicksort algorithm in javaaverage case time complexity of the quick sort algorithm is more than quick sort java 27why java uses quicksortqucik sort complexityquicksort injavaquicksort algorithmusquick sort implementation in javathe time complexity of quicksortquicksort pquicksort space complexitywhat is the best case efficiency for a quick sortquick sort complexity best casepartition sort nwhy is quicksort conquer trivialquick sorting algorithm methods in javapartition algorithmwhat is the average case complexity of quick sorthow does quicksort work 3fsimple java quick sort programquicks sort in javawhat is best case 2c worst case and average case complexity of quick sort 3fquick sort method java stringquicksort java