[C] 퀵 정렬

// quickSort.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

quickSort.cpp

#include "stdafx.h"

void swap(int &x, int &y)
{

 int t = x;

 x = y;

 y = t;

}

// 데이터를 기준값을 기준으로 두개의 블록으로 나눈다.
// A[]   [IN] 나눌 데이터
// p   [IN] 데이터의 첫번째 인덱스
// r   [IN] 데이터의 마지막 인덱스
// return  [OUT] 기준원소가 위치한 배열 인덱스

int partition(int A[], int p, int r)
{
 // i : 기준값보다 작은 데이터가 들어갈 곳
 // j : 배열을 처음부터 마지막까지 찾아봄
 // pivot : 기준 데이터

 int i = p;

 int j = p;

 int pivot = A[r];

 for( j = p; j <= r-1; j++)
 {

  if( A[j] < pivot )

swap(A[j], A[i++]);

 }
 swap(A[i], A[r]);

 return i;

}

// 데이터를 큇 정렬로 정렬한다.
// A[]   [IN] 나눌 데이터
// p   [IN] 데이터의 첫번째 인덱스
// r   [IN] 데이터의 마지막 인덱스

void quickSort(int A[], int p, int r)
{

 if( r <= p )

  return;

 int q = partition(A, p, r);
 
 quickSort(A, p, q-1);
 quickSort(A, q+1, r);

}

void Display(int A[], int n)
{

 for( int i = 0; i < n; i++)

  printf("%d ", A[i]);

 printf("\n");

}

int _tmain(int argc, _TCHAR* argv[])
{

 int A[] = { 3, 7, 1, 4, 9, 8, 2, 5, 10, 6 };

 Display(A, 10);
 quickSort(A, 0, 9);
 Display(A, 10);

 return 0;

}

실행 결과..

그래픽 요소 추가..

#include "stdafx.h"
#include <stdlib.h>
#include <windows.h>

void Display(int A[], int n);

void swap(int &x, int &y)
{

 int t = x;
 x = y;
 y = t;

}

// 데이터를 기준값을 기준으로 두개의 블록으로 나눈다.
// A[]   [IN] 나눌 데이터
// p   [IN] 데이터의 첫번째 인덱스
// r   [IN] 데이터의 마지막 인덱스
// return  [OUT] 기준원소가 위치한 배열 인덱스

int partition(int A[], int p, int r)
{
 // i : 기준값보다 작은 데이터가 들어갈 곳
 // j : 배열을 처음부터 마지막까지 찾아봄
 // pivot : 기준 데이터

 int i = p;
 int j = p;
 int pivot = A[r];

 for( j = p; j <= r-1; j++)
 {

  if( A[j] < pivot )

   swap(A[j], A[i++]);

 }
 swap(A[i], A[r]);

 return i;
}

// 데이터를 큇 정렬로 정렬한다.
// A[]   [IN] 나눌 데이터
// p   [IN] 데이터의 첫번째 인덱스
// r   [IN] 데이터의 마지막 인덱스

void quickSort(int A[], int p, int r)
{

 if( r <= p )

  return;

 int q = partition(A, p, r);
 
 quickSort(A, p, q-1);
 quickSort(A, q+1, r);

 Display(A, 20);

}

void Display(int A[], int n)
{

 const char *s = "############################################";
 system("cls");
 for( int i = 0; i < n; i++)

  printf("%3d : %.*s\n", A[i], A[i], s);

 Sleep(500);

}

int _tmain(int argc, _TCHAR* argv[])
{

 int A[40];

 for(int i = 0; i < 20; i++)

  A[i] = rand()%30+1;

 Display(A, 20);
 quickSort(A, 0, 19);
 Display(A, 20);

 return 0;

}

실행 결과..