Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lära Quicksort | Divide and Conquer Algorithms
Sorting Algorithms

Svep för att visa menyn

book
Quicksort

Quicksort is also a Divide and Conquer algorithm, and it is quite similar to the Merge sort algorithm. The main idea is to pick some pivot and partition all elements around it: elements less or equal – to the left side, and greater or equal – to the right one, and then sort these subarrays. That's the main difference with Merge Sort algorithm where the pivot element was the middle one.

There are many ways to pick the pivot element: pick the last element, the first one, random, etc. Here is an example with last elements as pivot.

partition(array, left, right) function builds a partitioned array around a pivot element with Time Complexity O(N). It returns the right index of the pivot element in array[left:right] and modifies the array according to the pivot.

quickSort() is a recursive sorting function similar to mergeSort(). It divides an array according to the pivot and recursively sorts the halves.

Time Complexity: O(NlogN) in average, but O(N^2) in the worst case.

The good case is when each time your pivot moves to the middle of an array during partition(). Then, this algorithm works like Merge Sort, where Time Complexity is O(NlogN). On average, pivot parties array on two arrays of almost the same length and reach this Time Complexity.

But the worst case is when your pivot parties array in subarrays of lengths N-1 and 1 each time. It can happen, if your array is already sorted, for example. Then, algorithm does O(N^2) operations (O(N) partitions for O(N) subarrays).

Space complexity: O(1)

Uppgift

Swipe to start coding

Follow the comments in code to implement the Quicksort algorithm. Test it for the given array arr.

Lösning

Switch to desktopByt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedan
Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 2
Vi beklagar att något gick fel. Vad hände?

Fråga AI

expand
ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

book
Quicksort

Quicksort is also a Divide and Conquer algorithm, and it is quite similar to the Merge sort algorithm. The main idea is to pick some pivot and partition all elements around it: elements less or equal – to the left side, and greater or equal – to the right one, and then sort these subarrays. That's the main difference with Merge Sort algorithm where the pivot element was the middle one.

There are many ways to pick the pivot element: pick the last element, the first one, random, etc. Here is an example with last elements as pivot.

partition(array, left, right) function builds a partitioned array around a pivot element with Time Complexity O(N). It returns the right index of the pivot element in array[left:right] and modifies the array according to the pivot.

quickSort() is a recursive sorting function similar to mergeSort(). It divides an array according to the pivot and recursively sorts the halves.

Time Complexity: O(NlogN) in average, but O(N^2) in the worst case.

The good case is when each time your pivot moves to the middle of an array during partition(). Then, this algorithm works like Merge Sort, where Time Complexity is O(NlogN). On average, pivot parties array on two arrays of almost the same length and reach this Time Complexity.

But the worst case is when your pivot parties array in subarrays of lengths N-1 and 1 each time. It can happen, if your array is already sorted, for example. Then, algorithm does O(N^2) operations (O(N) partitions for O(N) subarrays).

Space complexity: O(1)

Uppgift

Swipe to start coding

Follow the comments in code to implement the Quicksort algorithm. Test it for the given array arr.

Lösning

Switch to desktopByt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedan
Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 2
Switch to desktopByt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedan
Vi beklagar att något gick fel. Vad hände?
some-alt