Quicksort(퀵정렬)

Basic Concept

---

Quicksort is similar to Mergesort in that the sort is accomplished by dividing the array into two partitions and then sorting each partition recursively. However, in quicksort, the array is partitioned by placing all items smaller than some pivot item before that item and all items larger than the pivot item after it. The pivot item can be any item, and for convenience we will simply make it the first one.

 

Example The steps done by a human when sorting with Quicksort.

 

 

👉 퀵정렬은 정렬 대상 배열을 두 개의 파티션으로 나눈 다음 각 파티션을 재귀적으로 정렬한다는 점에서 합병정렬과 유사하다.

퀵정렬은 배열 분할시 피벗 값을 기준으로 피벗보다 작은 모든 항목을 피벗 값 앞에 배치하고, 피벗 값 보다 큰 모든 항목을 그 뒤에 배치한다. 피벗 값은 배열 내의 어떤 항목이든 사용 가능하나, 설명의 편의상 첫 번째 항목을 피벗 값으로 지정하였다.

 

 

Quicksort Algorithm

---

Algorithm Design

1. Partition the array so that all items smaller than the pivot item are to the left of it and all items larger are to the right.
2. Sort the subarrays.

 

👉 선택된 피벗 값을 기준으로 피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 오도록 배열을 분할하고 각 하위배열을 재귀적으로 정렬한다.​

 

Pseudo Code

• Quicksort

void quicksort(index low, index high)
{
  index pivotpoint;

  if (high > low) {
    partition(low, high, pivotpoint);
    quicksort(low, pivotpoint-1);
    quicksort(pivotpoint+1, high);
  }
}

void partition(index low, index high, index& pivotpoint)
{
  index i, j;
  keytype pivotitem;

  pivotitem = S[low]; // Choose first item for pivotitem.
  j = low;
  for (i = low+1; i <= high; i++)
    if (S[i] < pivotitem) {
      j++;
      exchange S[i] and S[j];
    }
    pivotpoint = j;
    exchange S[low] and S[pivotpoint]; // Put pivotitem at pivotpoint.
}

 

Source Code

• sorting.h

// File: sorting.h
#ifndef SORTING_H
#define SORTING_H

namespace algorithms
{
  void quicksort(int data[ ], int low, int high);
  // Problem: Sort n keys in nondecreasing order.
  // Inputs: positive integer n, array of keys S indexed from 1 to n.
  // Outputs: the array S containing the keys in nondecreasing order.

  void partition(int data[ ], int low, int high, int& pivotpoint);
  // Problem: Partition the array S for Quicksort.
  // Inputs: two indices, low and high, and the subarray of S indexed
  // from low to high.
  // Outputs: pivotpoint, the pivot point for the subarray indexed
  // from low to high.
}

#endif

 

• sorting.cpp

// File: sorting.cpp
#include <algorithm> // Provides swap
#include "sorting.h"

namespace algorithms
{
  void quicksort(int data[ ], int low, int high)
  {
    int pivotpoint;

    if (high > low)
    {
      partition(data, low, high, pivotpoint);
      quicksort(data, low, pivotpoint-1);  // before the pivotpoint
      quicksort(data, pivotpoint+1, high); // after the pivotpoint
    }
  }

  void partition(int data[ ], int low, int high, int& pivotpoint)
  {
    int i, j;
    int pivotitem;

    pivotitem = data[low]; // Choose first item for pivotitem.
    j = low;
    for (i = low+1; i <= high; ++i)
    {
      if (data[i] < pivotitem)
      {
        ++j;
        std::swap(data[i], data[j]);
      }
    }
    pivotpoint = j;
    std::swap(data[low], data[pivotpoint]); // Put pivotitem at pivotpoint.
  }
}

 

• sorttest.cpp

// File: sorttest.cpp
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include "sorting.h" // Provides sorting functions.
using namespace std;
using namespace algorithms;

// PROTOTYPE of a function that will test one of the sorting functions:
void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name);

void open_for_read(ifstream& f, const char filename[ ]);
// Postcondition: The ifstream f has been opened for reading using the given
// filename. If any errors occurred then an error message has been printed
// and the program has been halted.

bool is_more(istream& source);
// Precondition: input is an open istream.
// Postcondition: The return value is true if input still has more data to
// read; otherwise the return value is false.

void process_read(ifstream& f, int data[ ]);
// Precondition: input is an open istream.
// Postcondition: The values in inputfile are assigned to data array.

int main(int argc, char* argv[ ])
{  
  assert(argc == 2);
  testsort(quicksort, argv[1], "quicksort");

  return EXIT_SUCCESS;
}

void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name)
{

  const int ARRAY_SIZE = 100000;
  int data[ARRAY_SIZE];
  ifstream infile;

  open_for_read(infile, file_name);
  process_read(infile, data);
  infile.close( );

  clock_t start, end;  
  cout << "Testing the " << sorting_name << endl;
  start = clock( );
  sorter(data, 0, ARRAY_SIZE-1); // Sort the numbers
  end = clock( );

  // Check the sorting result.
  for (int i = 1; i < ARRAY_SIZE; ++i)
  {
    if (data[i-1] > data[i])
      exit(0);
  }
  cout << "Sorting completed correctly." << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << sorting_name << "'s elpased time is : "<< result << " sec." << endl;
}

void open_for_read(ifstream& f, const char filename[ ])
{
  f.open(filename);

  if (f.fail( ))
  {
    cerr << "Could not open input file." << endl;
    exit(0);
  }
}

bool is_more(ifstream& source)
{
  return (source && source.peek( ) != EOF);
}

void process_read(ifstream& f, int data[ ])
{
  size_t index = 0;

  while (is_more(f))
  {
    assert(f);
    f >> data[index];
    ++index;
  }
}

 

 

Time Complexity Analysis

---

Basic operation

the comparison of S[i] with pivotitem in partition.

 

Input size

n, the number of items in the array S.

 

Worst-Case Time Complexity

$\displaystyle W(n) = \frac{n(n-1)}{2} \in \Theta(n^{2})$

 

Average-Case Time Complexity

$A(n) \approx 1.38(n+1) logn \in \Theta (nlogn)$

 

👉 시간복잡도가 최악인 경우, 퀵정렬의 비교횟수는 $n^{2}$(quadratic time)을 요구한다. 하지만 정렬하고자 하는 키값들이 무작위로 분산되어 있다면,  퀵정렬이 평균적으로 수행하는 비교횟수는 $O(nlgn)$에 비례한다.

퀵정렬의 성능 향상을 위해서는 중간값에 가까운 피벗을 선택해야 한다. 선택된 피벗이 중간값에 가까울수록 좌우 파티션이 균등하게 이루어져 더 빨리 정렬할 수 있다. 위의 예시처럼 첫 번째 항목을 피벗으로 잡는 건 효율적이라고 할 수 없다. 피벗 값 선택시 랜덤하게 3~5개의 원소를 선택한 후, 그중에서 중간값을 취하는 방법도 있다.

퀵정렬은 합병정렬과 달리 정렬 과정에서 추가적인 작업 공간을 필요로 하지 않는 in-place sort이다.