QuickSort Algorithm

This is the QuickSort Algorithm.

The algorithm works by choosing a pivot element in the list (by default we can let this be the middle element in the list, but there are more complex variations that help decide what this should be), and then reordering the list so that the elements to the left (call this sub-list "small") of the pivot element are all less than the pivot element, and the elements to the right (call this sub-list "big") of the pivot element are all greater than the pivot element. So after the swap part of quicksort, the largest element of "small" will be less than the smallest element of "big". We then need to check on whether the sub-lists "small" and "big" need to be sorted, which is true if we have not considered those regions yet. In such a case, we call the procedure Quicksort on each of the sub-lists.

The pseudo-code for this algorithm is as follows:
QuickSort(A, left, right)
     i <- left
     j <- right
     pivot <- A[floor((left + right) / 2)]
     while (i <= j)
          while (A[i] < pivot)
               i <- i+1
          end while
          while (A[j] > pivot)
               j <- j-1
          end while
          if (i <= j)
               tmp <- A[i]
               A[i] <- A[j]
               A[j] <- tmp
               i <- i+1
               j <- j-1
          end if
     end while
     if (left < j)
          A <- QuickSort(A, left, j)
     end if
     if (i < right)
          A <- QuickSort(A, i, right)
     end if

     return A;
end QuickSort

Show Work?

Recent Updates

  • 08-10-2017 Floyd-Warshall Shortest Paths
  • 08-01-2017 Degree Centrality of a Graph
  • 06-03-2017 Tarjan's Strongly Connected Components Algorithm
  • 03-20-2017 Longest Common Subsequence
  • 10-27-2016 Independent Set Puzzles
  • 06-28-2016 Lets Learn About XOR Encryption
  • 06-15-2016 Discrete-time Markov Chains
  • 03-01-2016 Topological Sort
  • 01-21-2016 The RSA Algorithm
  • 11-20-2015 How To Take Notes in Math Class
  • 10-28-2015 The Depth-First-Search Algorithm
  • 10-28-2015 The Breadth-First-Search Algorithm
  • 09-23-2015 ID3 Algorithm Decision Trees
  • 07-08-2015 Clique Problem Puzzles
  • 06-25-2015 Unidirectional TSP Puzzles
  • 04-04-2015 Learn About Descriptive Statistics
  • 02-19-2015 Slope Formula
  • 01-15-2015 Interactive Midpoint Formula
  • 12-18-2014 Triangle Sum Puzzle
  • 12-02-2014 The Bridge Crossing Problem