인프런 커뮤니티 질문&답변
작성한 질문수
qsort 함수 질문
작성
·
317
0
qsort를 직접 구현하고싶어서 이것저것 시도하던중 의문점이 생긴게 몇게 있어서 질문을 남깁니다.
1.
int arr[] = { 8, 2, 5, 3, 6, 11};
int compare(const void* first, const void* second)
{
if (*(int*)first > * (int*)second)
return 1;
else if (*(int*)first < *(int*)second)
return -1;
else
return 0;
}
의 함수에서 first와 second가 갖는 주소값이
이런식으로 second가 arr[0]의 주소값을 갖고 first가 arr[1]를 갖는데 qsort함수를 사용법을 검색했을때
첫번째 변수가 두번째 변수보다 클때 1을 반환하고
작을때 -1을 반환하면 오름차순으로 정렬된다고 나오는데
첫번째 변수의 값이 second 에 들어갈까요 ㅠ
2. qsort라는 함수를 검색했을때 분할정복이라는 알고리즘을 통해 구현되있다고 쉽게 찾아볼수 있었습니다.
그러나 막상 디버그를 돌리면 compare함수 안에서
후
이런식으로 가장 큰 값이 순차적으로 뒤로 가는걸 확인할수 있었는데
제가 찾아본 분할정복하고는 값이 정리되는 방식이 많이 달라서 혼란을 격고있습니다.
qsort함수는 분할정복 알고리즘을 사용한거가 맞는건가요?
혹시 qsort함수가 어떤식으로 구현됐는지 확인할수 있는 방법도 알 수 있을까요?
답변 2
1
안녕하세요!
1. 1번은 무슨 말씀인지 잘 와닿지가 않는데 "첫번째 변수의 값이 second 에 들어갈까요 ㅠ" 라고 말씀하신 의미가 더 앞에있는 원소의 주소가 왜 first가 아닌 second 매개 변수로 넘어가냐는 말씀이 맞을까요? 퀵소트는 기준 원소(pivot) 하나를 정해놓고 그 기준이 되는 원소와 나머지 다른 원소들을 비교하는 알고리즘입니다. 내부적으로 비교 대상이 되는 원소를 비교 함수의 첫 번째 인수로 넘기고 기준이 되는 원소는 두 번째 인수로 넘기는게 아닐까 추측이 됩니다. 저도 정확히 내부적으로 어떻게 굴러가는지는 잘 모르겠지만 (구글링을 해봤는데 찾기가 쉽지 않네요) 더 앞에 있던 원소가 qsort 함수가 정렬하는 방식 상에서의 피봇이였던게 아닐까 싶어요. 그저 제 추측입니다.
2. qsort 함수는 일반적으로 알고리즘 전공책에 등장하는 그 퀵소트 방식이랑은 다를거에요. 퀵소트 방식이라고 일반적으로 알려진, 우리가 책에서 배우는 그 퀵소트를 좀 더 빠르게, 최악의 경우를 더 줄이게끔, 최적화 되도록 좀 변형되서 구현되어져 있는 것 같아요. 피봇을 선택하는 방식도 다르고 아무튼 우리가 배운 그 퀵소트 방식이랑은 조금 다르게, 더 빠르게 구현되어 있다고 알고 있습니다. 질문자님의 글과 비슷한 질문글 링크들인데 참고하시면 도움 되실겁니다.
https://stackoverflow.com/questions/16193483/is-qsort-really-quicksort?
https://stackoverflow.com/questions/13353904/what-sorting-algorithm-does-qsort-use
https://stackoverflow.com/questions/3485974/quicksort-implementation-in-c
stdlib 라이브러리의 qsort 코드입니다.
0
감사합니다! 도움이 많이 됐습니다!
첫번째 질문을 제가 설명을 잘 못했네요,
답변해주신대로 second에 원소 주소가 넘어가는거에 대해 궁금증을 가지고 있었는데 잘 이해해주셨네요 ㅠ
궁금증이 많이 해소 됐습니다!! 감사합니다!