Selection Sort 정렬이 제대로 안되네요..
글쓴이: shs0917 / 작성시간: 금, 2004/03/05 - 11:58오전
#include <stdio.h> #define MAX 100 int swap(int *, int *); int sort(int [], int); int main(void){ int index, n; int data[MAX]; printf("Enter the n: "); scanf("%d", &n); if(n < 1 || n > MAX){ fprintf(stderr, "Input error\n"); exit(1); } for(index = 0; index < n; index++){ data[index] = rand() % 100; printf("%d ", data[index]); } printf("Created data:\n"); if(sort(data, n) != 0){ fprintf(stderr, "Sort error!\n"); } printf("Selection sorted data:\n"); for(index = 0; index < n; index++){ printf("%d ", data[index]); } printf("End\n"); } int swap(int *x, int *y){ int tmp = *x; *x = *y; *y = tmp; return 0; } int sort(int sdata[], int sn){ int index1, index2, min; for(index1 = 0; index1 < sn - 1; index1++){ min = index1; for(index2 = index1 + 1; index2 < sn; index2++){ if(sdata[min] > sdata[index2]){ min = index2; } } if(swap(&sdata[min], &sdata[index2]) != 0){ fprintf(stderr, "Swap error!\n"); } } return 0; }
버블 소트랑은 뭐가 다른건지.. 쩝..
알고리즘을 거의 공부를 안해서요..
그리고 이 소스 제대로 정렬이 안되네요..
Forums:
중간에 실행오류 안나나요?
swap 호출이 잘못되었군요.
swap(&sdata[min], &sdata[index2]) 이 아니라
swap(&sdata[min], &sdata[index1]) 입니다.
Bubble Sort 는 인접위치를 비교하는 방식입니다.
최대값이 마치 거품이 점점 떠오른다는 느낌에서 지어진 이름이 아닐까 싶습니다.
최소값이 거꾸로 가라앉는다는 관점으로 봐서 Sinking Sort 라고도 합니다.
값의 대입이 많이 이루어지기 때문에 O(n^2 ) 중에서 Bubble Sort 는 효율적이지 않습니다.
사실 값의 대입에 있어서는 Selection Sort 가 가장 효율적입니다.
(시간복잡도 차수에 있어서는...)
정렬이 이루어지는 것을 확실히 보고 싶다면
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=free&no=8345
Borland Forum 자유게시판
정렬에 대한 자세한 설명과 예제 source 를 보고 싶다면
http://en.wikipedia.org/wiki/Sort_algorithm
Wikipedia
그런데 O(n^2) 정렬은 정확한 방법이 무엇이든 그냥 Bubble Sort 라고 말하는 사람이 많더군요.
답변 너무 감사드립니다.. 저렇게 간단한 것을 알아채지 못했다니..
답변 너무 감사드립니다..
저렇게 간단한 것을 알아채지 못했다니..
스스로 좀 더 알아봤어야 하는건데..
앞으로는 좀 더 신중히 공부하고 질문을 올려야 겠네요..
컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러
댓글 달기