설명#

The quick sort is an in-place, divide-and-conquer, massively recursive sort. As a normal person would say, it's essentially a faster in-place version of the merge sort. The quick sort algorithm is simple in theory, but very difficult to put into code (computer scientists tied themselves into knots for years trying to write a practical implementation of the algorithm, and it still has that effect on university students).

The recursive algorithm consists of four steps (which closely resemble the merge sort):

1. If there are one or less elements in the array to be sorted, return immediately. 2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.) 3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot. 4. Recursively repeat the algorithm for both halves of the original array.

The efficiency of the algorithm is majorly impacted by which element is choosen as the pivot point. The worst-case efficiency of the quick sort, O(n2), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn't random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(n log n).

The quick sort is by far the fastest of the common sorting algorithms. It's possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn't anything faster.

As soon as students figure this out, their immediate implulse is to use the quick sort for everything - after all, faster is better, right? It's important to resist this urge - the quick sort isn't always the best choice. As mentioned earlier, it's massively recursive (which means that for very large sorts, you can run the system out of stack space pretty easily). It's also a complex algorithm - a little too complex to make it practical for a one-time sort of 25 items, for example.

With that said, in most cases the quick sort is the best choice if speed is important (and it almost always is). Use it for repetitive sorting, sorting of medium to large lists, and as a default choice when you're not really sure which sorting algorithm to use. Ironically, the quick sort has horrible efficiency when operating on lists that are mostly sorted in either forward or reverse order - avoid it in those situations.

  • 장점: 굉장히 빠름.
  • 단점: 매우 복잡한 알고리즘이고 재귀적이다.

실행횟수

O(n log n)

자바 소스#

public class QuickSort {

  public static void sort(int numbers[]) {
    int array_size = numbers.length;
    q_sort(numbers, 0, array_size - 1);
  }

  public static void q_sort(int numbers[]int left, int right) {
    int pivot, l_hold, r_hold;

    l_hold = left;
    r_hold = right;
    pivot = numbers[left];
    while (left < right) {
      while ((numbers[right>= pivot&& (left < right))
        right--;
      if (left != right) {
        numbers[left= numbers[right];
        left++;
      }
      while ((numbers[left<= pivot&& (left < right))
        left++;
      if (left != right) {
        numbers[right= numbers[left];
        right--;
      }
    }
    numbers[left= pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;
    if (left < pivot)
      q_sort(numbers, left, pivot - 1);
    if (right > pivot)
      q_sort(numbers, pivot + 1, right);
  }

  public static void main(String[] args) {
    int[] a = 4731582};
    sort(a);
    for (int i = 0; i < a.length; i++)
      System.out.print(a[i"  ");
  }
}

효율성#

quick.jpg

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
jpg
quick.jpg 29.3 kB 1 14-Jul-2007 21:43 DongGukLee
« This page (revision-1) was last changed on 14-Jul-2007 21:43 by DongGukLee