본문 바로가기

CS/알고리즘

[C] quickSort 알고리즘

#include <stdio.h>
void printArray(int arr[], int length);
void quickSort(int arr[], int left, int right);
int q = 1;

int main(void) {
  int arr[6] = {2, 4, 3, 5, 1, 0};

  printf("\nBefore Sorting : ");
  printArray(arr, 6);
  printf("\n");

  quickSort(arr, 0, 5);

  printf("\nAfter Sorting : ");
  printArray(arr, 6);
}

void quickSort(int arr[], int left, int right) {
  int leftCounter = left;
  int rightCounter = right;
  int pivot = arr[(leftCounter + rightCounter) / 2];
  int temp;

  printf("%dth Sort, left = %d, right = %d\n", q, left, right);
  q++;

  while (leftCounter <= rightCounter) {
    while (arr[leftCounter] < pivot)
      leftCounter++;

    while (arr[rightCounter] > pivot)
      rightCounter--;

    if (leftCounter <= rightCounter) {
      temp = arr[leftCounter];
      arr[leftCounter] = arr[rightCounter];
      arr[rightCounter] = temp;
      leftCounter++;
      rightCounter--;
    }
  }

  if (leftCounter < right)
    quickSort(arr, leftCounter, right);
  if (rightCounter > left)
    quickSort(arr, left, rightCounter);
}

void printArray(int arr[], int length) {
  for (int i = 0; i < length; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}
Before Sorting : 2 4 3 5 1 0 

1th Sort, left = 0, right = 5
2th Sort, left = 3, right = 5
3th Sort, left = 4, right = 5
4th Sort, left = 0, right = 2
5th Sort, left = 1, right = 2

After Sorting : 0 1 2 3 4 5

'CS > 알고리즘' 카테고리의 다른 글

[C] Merge Sort 알고리즘 (합병 정렬)  (2) 2024.10.22