현재 위치

홈 ›› Forums ›› 재미 ›› 자유 게시판

머리를 긁적이게 만드는 소팅 알고리즘 : Stooge Sort

dl3zp3의 이미지
글쓴이: dl3zp3 / 작성시간: 일, 2009/04/12 - 2:16오전

http://en.wikipedia.org/wiki/Stooge_sort

간단한 알고리즘인데 왜 제대로 작동하는지 이해하려면 약간 생각해봐하는 알고리즘이죠.

Forums: 
자유 게시판
plustag의 이미지

글쓴이: plustag / 작성시간: 일, 2009/04/12 - 12:55오후

학교다닐때 알고리즘 시험문제였습니다..
1. 저게 왜 정렬이 되는지 증명하라.
2. 복잡도를 계산하라.
다들 시험지를 보자마자 멍했죠..
시험보기 전주에 교수님이 친절히 지난 5년간의 족보를 주시는 분이라.. 요령으로는 택도 없는..

누가 저런 소팅을 쓰냐고 궁시렁거렸던적이 있었습니다..

누구냐 넌?

dl3zp3의 이미지

글쓴이: dl3zp3 / 작성시간: 일, 2009/04/12 - 7:59오후

2번은 그렇게 어려운 문제는 아닌듯.. 1번은 좀 생각을 해봐야하지만..

ahsan의 이미지

글쓴이: ahsan / 작성시간: 일, 2009/04/12 - 6:19오후

if L[j] < L[i] then
L[i] ↔ L[j]
이부분 값을 바꾸라는 말 같은데 재대로 모르겠네요

누가 C로 좀 보여줘봐요?

iamt의 이미지

글쓴이: iamt / 작성시간: 일, 2009/04/12 - 6:38오후

서로 값을 바꾸라는 의미로 스왑입니다.

C소스는 찾아보니 다음과 같네요.

/*
 
     STOOGE SORT
     Written by Sanchit Karve AKA born2c0de
     born2c0de AT hotmail DOT com
*/
 
 
#include <stdio>
 
#define ELEMENTS 6
 
void stoogesort(int A[],int i,int j)
{
   int tmp,k;
   if(A[i]>A[j])
   {
        tmp=A[i];
      A[i]=A[j];
      A[j]=tmp;
   }
   if((i+1)>=j)
        return;
 
   k=(int)((j-i+1)/3);   // Round down
   stoogesort(A,i,j-k);  // First two-thirds
   stoogesort(A,i+k,j);  // Last two-thirds
   stoogesort(A,i,j-k);  // First two-thirds again
}
 
int main()
{
  int i;
  int X[ELEMENTS]={5,2,4,6,1,3};
  printf("Unsorted Array:\n");
  for(i=0;i<ELEMENTS;i++)
            printf("%d ",X[i]);
 
  stoogesort(X,0,ELEMENTS);
  printf("\nSORTED ARRAY\n");
  for(i=0;i<ELEMENTS;i++)
            printf("%d ",X[i]);
 
}

---------------------------------------------------------------------------------
C(++)과 php 펄등을 공부하고있습니다.
반갑습니다! 리눅스 :-)

---------------------------------------------------------------------------------
C(++)과 php 펄등을 공부하고있습니다.
반갑습니다! 리눅스 :-)

ahsan의 이미지

글쓴이: ahsan / 작성시간: 일, 2009/04/12 - 8:49오후

위의 코드를 실행해 보니 이해가 안됨.

#include

#define ELEMENTS 11

void stoogesort(int A[],int i,int j)
{
int tmp,k;
if(A[i]>A[j])
{
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
if((i+1)>=j)
return;

k=(int)((j-i+1)/3); // Round down
stoogesort(A,i,j-k); // First two-thirds
stoogesort(A,i+k,j); // Last two-thirds
stoogesort(A,i,j-k); // First two-thirds again
}

int main()
{
int i;
int X[ELEMENTS]={500,200,400,600,100,300,23,45,67,98,34};
printf("Unsorted Array:\n");

for(i=0;i < ELEMENTS; i++)
printf("%d ",X[i]);

stoogesort(X,0,ELEMENTS);
printf("\nSORTED ARRAY\n");
for(i=0;i < ELEMENTS; i++)
printf("%d ",X[i]);
putchar('\n');
}

===========결과======================
Unsorted Array:
500 200 400 600 100 300 23 45 67 98 34
SORTED ARRAY
11 23 34 45 67 98 100 200 300 400 500

600이 사라지고, 11이 나타났습니다
왜 이렇게 나오는거죠?

송효진의 이미지

글쓴이: 송효진 / 작성시간: 일, 2009/04/12 - 8:50오후

stoogesort(X,0,ELEMENTS-1); 로 하면 될거에요.

emerge money
http://wiki.kldp.org/wiki.php/GentooInstallSimple - 명령어도 몇 개 안돼요~
http://xenosi.de/

https://xenosi.de/

송효진의 이미지

글쓴이: 송효진 / 작성시간: 일, 2009/04/12 - 7:09오후

한번 돌려보니까 재귀가 엄청난데요.
버블소트 루프의 3배 이상의 재귀호출이 발생하네요.
이건 어떤때 쓰는 알고리즘인가요?

emerge money
http://wiki.kldp.org/wiki.php/GentooInstallSimple - 명령어도 몇 개 안돼요~
http://xenosi.de/

https://xenosi.de/

dl3zp3의 이미지

글쓴이: dl3zp3 / 작성시간: 일, 2009/04/12 - 8:03오후

비효율적이니까 어디에서 쓰라고 만든 건 아닌 것 같고 시험문제용으로 좋은 알고리즘인 것 같습니다.

vamf12의 이미지

글쓴이: vamf12 / 작성시간: 월, 2009/04/13 - 6:03오후

The running time of the algorithm is thus extremely slow compared to efficient sorting algorithms, such as Merge sort.
무지하게 느린 정렬이라는 군요.. ㅎ
The algorithm gets is name from slapstick routines of the Three Stooges, in which each stooge hits the other two.
거기다 슬랩 스틱 수준이라는... -_-

JuEUS-U의 이미지

글쓴이: JuEUS-U / 작성시간: 월, 2009/04/13 - 1:07오전

헐,, 어렵지는 않지만 시험문제로 나오긴 좀 뭐하지 싶습니다 = _=);;

알고리즘은 데이터가 3개의 섹션으로 나뉘었다고 가정하고
1) 앞/가운데 섹션을 소트
2) 가운데/뒤 섹션을 소트
3) 앞/가운데 섹션을 소트

- 1단계 후, (앞)i <= (가운데)j (i,j,k는 섹션별 임의의 아이템 인덱스)
- 2단계 후, (가운데)j <= (뒤)k
단, 여기서 (앞)i <= (뒤)k이다.

- 3단계 후, (앞)i <= (가운데)j
- 결국 (앞)i <= (가운데)j <= (뒤)k

둘러보기