Selection Sort 정렬이 제대로 안되네요..

shs0917의 이미지

#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;
}


버블 소트랑은 뭐가 다른건지.. 쩝..
알고리즘을 거의 공부를 안해서요..
그리고 이 소스 제대로 정렬이 안되네요..
winner의 이미지

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 라고 말하는 사람이 많더군요.

shs0917의 이미지

답변 너무 감사드립니다..
저렇게 간단한 것을 알아채지 못했다니..
스스로 좀 더 알아봤어야 하는건데..
앞으로는 좀 더 신중히 공부하고 질문을 올려야 겠네요..

컴퓨터가 이해할수 있는 코드는 어느 바보나 다 작성할 수 있다. 좋은 프로그래머는 사람이 이해할 수 있는 코드를 짠다 - 마틴파울러

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.