Quicksort

• Algorithms Lesson 4: Quicksort

http://www.youtube.com/watch?v=y_G9BkAm6B8&feature=relmfu
partition step

• Visualization of Quick Sort

http://www.youtube.com/watch?v=vxENKlcs2Tw

• Quick Sort

http://www.youtube.com/watch?v=J7FTIe5y3Mw&feature=related

• QuickSort

http://www.youtube.com/watch?v=Fju_NstEy3M

• Lec-11 Mergesort And Quicksort

http://www.youtube.com/watch?v=KrjWloKRE2U&feature=related

• Quicksort

Quicksort is a sorting algorithm
In the worst case, it makes O(n2) comparisons
Quicksort is often faster in practice than other O(n log n) algorithms

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:
Pick an element, called a pivot, from the list.

Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

function quicksort('array')
      if length('array') = 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' = 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls
     
http://en.wikipedia.org/wiki/Quicksort

• Quicksort

Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice

Java

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
   
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
   
      return i;
}

void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

http://www.algolist.net/Algorithms/Sorting/Quicksort

• Quick Sort is a sorting algorithm which uses divide and conquer technique.

In quick sort we choose an element as a pivot and we create a partition of array around that pivot. by repeating this technique for each partition we get our array sorted

depending on the position of the pivot we can apply quick sort in different ways

taking first or last element as pivot

taking median element as pivot

Time Complexity Analysis of Quick Sort

The average time complexity of quick sort is O(N log(N)).

Best case Time Complexity of Quick Sort

O(Nlog(N))

the best case of quick sort is when we will select pivot as a mean element.

Worst Case Time Complexity of Quick Sort

O(N^2)

This will happen when we will when our array will be sorted and we select smallest or largest indexed element as pivot

Average Case Time Complexity of Quick Sort

O(Nlog(N))

Space Complexity

O(N)

https://iq.opengenus.org/time-and-space-complexity-of-quick-sort/