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 라고 말하는 사람이 많더군요.
답변 너무 감사드립니다.. 저렇게 간단한 것을 알아채지 못했다니..
답변 너무 감사드립니다..
저렇게 간단한 것을 알아채지 못했다니..
스스로 좀 더 알아봤어야 하는건데..
앞으로는 좀 더 신중히 공부하고 질문을 올려야 겠네요..
컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러
댓글 달기