[C언어] 퀵정렬 함수 qsort

⚠️ 내맘대로하는 설명이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

오늘은 qsort라고도 부르는 퀵정렬에 대해서 알아볼거다. 

 

qsort는 배열을 순서대로 정렬하는 기능을 한다. 당연히 숫자도 가능하고, 문자도 가능하다.

그럼 어떨때 사용할까? 무작위로 입력을 받은 배열에서 내가 원하는 값을 찾아낼때 정렬을 한 후 이진탐색을 한다거나, 사전순 출력을 할때 주로 사용한다.

 

qsort는 헤더파일 <stdlib.h>에서 제공하는 함수이다. 인자는 총 4개를 받는다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *)

base는 정렬하고자 하는 배열

nel은 정렬하고자 하는 배열의 크기

width는 정렬하고자 하는 배열의 원소 하나의 크기

compare는 비교함수이다. 

 

int number[5] = {3, 2, 4, 5, 1}; 라는 배열이 있고, 정렬을 하고자 한다고 치자.

base는 이 배열의 이름인 number 가 된다.

nel은 이 배열의 크기인 5가 된다.

width는 이 배열의 원소 하나의 크기, 즉 int 하나의 크기를 나타낸다. sizeof(int)를 사용하면 쉽게 구할 수 있다.

compare함수의 경우는 밑에서 자세히 설명하겠다.

 

int compare(const void *a, const void *b) // 오름차순 정렬

{

    int num1 = *(int *)a;

    int num2 = *(int *)b; 

 

    if (num1 < num2) 

        return -1; 

    

    if (num1 > num2)

        return 1;  

    

    return 0;  

}

compare함수는 사용자가 직접 정의해서 사용하는 함수이다. 이 함수를 보면서 왜 qsort내부에 포함시켜둔게 아니라 내가 코드를 짜서 사용해야하는지 의문이 생길 수도 있다. 이는 오히려 사용자를 위한 배려다. 만약 compare함수를 사용자가 직접 짜는게 아니라, qsort내부에 있었다면 활용이 불가능해진다. 지금 위에있는 코드는 오름차순 정렬로 출력하지만, return값만 손본다면 내림차순으로도 정렬이 가능해진다. if(num1<num2)일때 -1이 아닌 1을 리턴하고, if(num1>num2)일때 -1을 리턴할 경우 내림차순이 된다. 

 

이걸 사용한 예시는 내 블로그에 "[C언어] 백준 2108번 : 통계학" 문제 풀이가 있다. 온김에 한번 보고 가주라ㅎ. 

https://naemamdaelo.tistory.com/6?category=1005618 

[C언어] 백준 2108번 : 통계학

 

그러고보니까 bubble정렬이나 다른 정렬이 많은데 왜 qsort를 써야할까?

이름부터 Quick이잖냐. 제일 빠르다.

 

 

 

-꿑-