Bubble Sort의 용도는?

resnick의 이미지

제가 알고리즘 책을 볼때마다 느끼는 의문이 있는데, 버블소트는 대체 무슨 용도가 있는가 하는 것입니다.

최악의 정렬 알고리즘으로 유명한데도 불구하고 거의 모든 알고리즘 책에 빠짐없이 등장하는걸 보면 나름대로 이유가 있을 법한데...

버블 소트의 활용법(?)에 대해 토의해 보는 자리가 되었으면 좋겠습니다.

제가 생각하기에, 자기 테이프같이 random access가 안되는 저장장치에서 대용량 자료를 정렬할때 라던가 단일 연결 리스트같은 자료구조에서는 버블 소트가 가장 나은 선택으로 보입니다만... 어떻게 생각하십니까?

익명 사용자의 이미지

단 대섯줄을 추가하면 간단히 소팅할 수 있게 됩니다.

어떤 경우 매우 유용하죠.

나는오리의 이미지

resnick wrote:
제가 알고리즘 책을 볼때마다 느끼는 의문이 있는데, 버블소트는 대체 무슨 용도가 있는가 하는 것입니다.

최악의 정렬 알고리즘으로 유명한데도 불구하고 거의 모든 알고리즘 책에 빠짐없이 등장하는걸 보면 나름대로 이유가 있을 법한데...

버블 소트의 활용법(?)에 대해 토의해 보는 자리가 되었으면 좋겠습니다.

제가 생각하기에, 자기 테이프같이 random access가 안되는 저장장치에서 대용량 자료를 정렬할때 라던가 단일 연결 리스트같은 자료구조에서는 버블 소트가 가장 나은 선택으로 보입니다만... 어떻게 생각하십니까?

알고리즘은 어떤것이 가장 좋다는 생각을 가지면 안됩니다.
어떠한 환경에서 어떤 알고리즘이 가장 좋을까를 생각해야 합니다.
그리고 한가지 알고리즘으로 해결하기보단 두,세가지의 알고리즘을 써야할 때도 있습니다.

이런 컴퓨터라면 알고리즘을 한가지만 써도 충분하고 안써도 될 정도겠지요. ^^;

cinsk의 이미지

Quote:
어떠한 환경에서 어떤 알고리즘이 가장 좋을까를 생각해야 합니다.

맞습니다. 좀 덧붙이자면 말씀하신 random access가 가능한지도 여기에 포함될 것이고, sorting할 대상이 배열, 또는 리스트에 들어 있는가? index가 준비되어 있는가? 메모리는 충분한가? 대상의 갯수가 무한정 커질 수 있는가? 등등을 고려해야 합니다.

O(N^2)의 정렬 알고리즘이 O(N * log(N))보다 항상 나쁜 것은 아닙니다. 예를 들어, 정렬 대상이 작거나 고정된 경우나 메모리가 매우 작은 경우등의 환경에서 O(N * log(N))보다 나을 수도 있습니다.

알고리즘을 배울 때는 N이 무한대일 경우의 시간/공간만을 따지기 쉽지만, 실제로 개발할 때에는 N이 무한대일 경우가 없지는 않겠지만, 유한하거나, 크지 않는 경우도 많기 때문에, 고려해야 할 사항이 많아집니다.

cronex의 이미지

inserting sort도 O( N^2 ) 의 알고리즘이지만
이미 대부분 정렬되어있는 아이템들에 대해서 정렬을 하면 매우 빠르죠.
그래서 정렬되어 있는 리스트에 아이템들이 조금씩 업데이트 되는 경우 inserting sort를 사용하면 빠른 결과를 얻습니다.
반대로 일반적으로 가장 빠른 sorting 알고리즘인 quick sort의 경우 이미 정렬된 아이템들에 대해서 정렬을 하면 최악의 시간이 걸립니다. O( N^2)

그리고 버블소트가 알고리즘 책마다 나오는 건 간단하다는데 있겠죠. 가장 이해하기 쉽고 또한 가장 느리기 때문에 다른 sorting 알고리즘과의 비교목적에서 항상 등장하는게 아닐까 합니다.

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

creativeidler의 이미지

필요한 곳에 필요한 알고리즘을 쓰는 것이 일반론으로는 옳은 말이지만 '버블 소트가 정말로 필요한 경우가 어디냐?' 하면 '없다'가 정답이죠. 알고리즘 책에 나오는 이유는 "학습용"이라고 보시면 되겠습니다-_-

freezm7의 이미지

creativeidler wrote:
필요한 곳에 필요한 알고리즘을 쓰는 것이 일반론으로는 옳은 말이지만 '버블 소트가 정말로 필요한 경우가 어디냐?' 하면 '없다'가 정답이죠. 알고리즘 책에 나오는 이유는 "학습용"이라고 보시면 되겠습니다-_-

PC 쪽만 생각하시는것 아닌가 싶습니다.
전 얼마전에 RAM 256 Bytes 에 프로그램 메모리 1KBytes 짜리
마이컴에서 소팅이 필요했었습니다.

이런 환경에서 퀵소트의 복잡한 코드로 프로그램 메모리를 다 잡아 먹을 이유는 없죠.
버블소트가 정말로 필요한 곳도 분명 있습니다.

즐겁게 살아 볼까나~*

정태영의 이미지

버블소트가 퀵소트등보다 언제나 느린건 아닙니다 ...

sorting 해야할 양이 적은 경우는 quick sort 보다 bubble sort 가 더 빠릅니다... (libc 에 있는 qsort 도 크기가 작은 경우엔 bubble sort 로 하는 걸로 압니다)

qsort 의 복잡도 n logN 은 이상적인 경우의 결과값입니다... 정렬이 다 되어있는 걸 다시 정렬하게 된다거나 할 경우 n^2 이 나오며;; 실제론 bubble sort 보다 복잡하니... 더 느릴 수밖에 없죠 ;)

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

addnull의 이미지

우선 bubble sort가 가장 느린 건 아닙니다.
time complexity 상으로 둘다 O(N^2)이라지만
selection sort가 더 느립니다..
bubble sort는 정렬 도중에 이미 정렬이 끝났음을 판단할 수 있죠.

creativeidler wrote:
필요한 곳에 필요한 알고리즘을 쓰는 것이 일반론으로는 옳은 말이지만 '버블 소트가 정말로 필요한 경우가 어디냐?' 하면 '없다'가 정답이죠. 알고리즘 책에 나오는 이유는 "학습용"이라고 보시면 되겠습니다-_-

음. 글쎄요....
"사다리 타기" 게임에서 bubble sort가 쓰이긴 합니다.
사다리 위의 번호와 아래의 번호들이 주어졌을 때,
해당 사다리의 모양을 찾는 게임인데,
bubble sort를 하면 사다리의 모양이 나오죠.

2005년 11월 10일.

전웅의 이미지

resnick wrote:
제가 알고리즘 책을 볼때마다 느끼는 의문이 있는데, 버블소트는 대체 무슨 용도가 있는가 하는 것입니다.

최악의 정렬 알고리즘으로 유명한데도 불구하고 거의 모든 알고리즘 책에 빠짐없이 등장하는걸 보면 나름대로 이유가 있을 법한데...

버블 소트의 활용법(?)에 대해 토의해 보는 자리가 되었으면 좋겠습니다.

제가 생각하기에, 자기 테이프같이 random access가 안되는 저장장치에서 대용량 자료를 정렬할때 라던가 단일 연결 리스트같은 자료구조에서는 버블 소트가 가장 나은 선택으로 보입니다만... 어떻게 생각하십니까?

활용법이라면... 사다리 타기 구현할 때 --;

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

creativeidler의 이미지

Quote:
PC 쪽만 생각하시는것 아닌가 싶습니다.
전 얼마전에 RAM 256 Bytes 에 프로그램 메모리 1KBytes 짜리
마이컴에서 소팅이 필요했었습니다.

이런 환경에서 퀵소트의 복잡한 코드로 프로그램 메모리를 다 잡아 먹을 이유는 없죠.
버블소트가 정말로 필요한 곳도 분명 있습니다.

퀵소트도 구현하기에 따라서 10라인 정도로 구현 가능합니다. 결코 메모리를 다 잡아먹을 정도로 복잡하지 않죠.

근데 프로그램 메모리 1KB 짜리의 마이컴을 써야하는 환경인데 소팅이 필요하다? 어떤 환경인지 궁금하군요. 뭘 개발하시는 것인가요? 요즘 소팅 알고리즘을 돌릴 수 있을 정도의 프로세서를 쓰는 곳은 프로그램 메모리 1KB 이런 경우가 없는 걸로 알고 있습니다만. 거기다 메모리 256 바이트면 소팅해야할 데이터나 제대로 들어가는지가 의문이군요. Z80같은 학습용 프로젝트가 아닌 바에야..

그리고 물론 버블 소트가 퀵소트보다 빠른 경우도 있죠. 하지만 이런 경우는 어차피 전체 수행시간이 짧기 때문에 어떤 소트 알고리즘을 쓰든 별 상관 없죠. 사다리에 퀵 소트를 쓰든 버블 소트를 쓰든 별 상관 있겠습니까? 어차피 0.01초에 끝날 일이 0.0099초에 끝나든지 하는 정도의 차이겠죠.

익명 사용자의 이미지

creativeidler wrote:
사다리에 퀵 소트를 쓰든 버블 소트를 쓰든 별 상관 있겠습니까? 어차피 0.01초에 끝날 일이 0.0099초에 끝나든지 하는 정도의 차이겠죠.

off topic 입니다. :)

사다리에 퀵 소트를 쓰면 안될겁니다. 버블소트의 인접 두 요소들의 비교, 교환의 특성을 쓰는 게 아닐까 싶네요. :)

insertion 소트의 경우 다른 n lg n 소트들의 일부로서 들어가기도 하지만 bubble 소트의 경우 얼마나 쓸 지는 모르겠습니다. 그야말로 소트엔 이런것들이 있다! 하면서 나오는 게 전부지요. 버블의 개량판인 shell 소트 같은 경우는 나름대로 쓰는 데가 있다고 하니 그런가보다 하고요. ( 책에 나오는 이야기긴 합니다. )

전웅의 이미지

creativeidler wrote:
그리고 물론 버블 소트가 퀵소트보다 빠른 경우도 있죠. 하지만 이런 경우는 어차피 전체 수행시간이 짧기 때문에 어떤 소트 알고리즘을 쓰든 별 상관 없죠. 사다리에 퀵 소트를 쓰든 버블 소트를 쓰든 별 상관 있겠습니까? 어차피 0.01초에 끝날 일이 0.0099초에 끝나든지 하는 정도의 차이겠죠.

"전통적인" 사다리 타기에서 중요한 것은 소팅 시간이 아니라 "올바른"
사다리를 생성하는 것입니다. 이때 버블 소트가 쓰이는 이유는 정렬이
인접한 요소 사이의 교환 만으로 이루어진다는 점입니다.

예를 들어, "사다리 타기에서 서로 다른 곳에서 출발한 두 사람은 항상
서로 다른 곳으로 도착함을 증명하라"라고 묻는다면 사다리 타기 문제가
결국 버블 소트에 사상된다는 점만 보이면 문제는 해결됩니다.

알고리즘에 따라 특정 상황에서 유리한, 또 다른 상황에서는 불리한
알고리즘이 있지만, 성능 이외에 알고리즘의 또 다른 특성 중 하나는 어떤
이해 및 구현의 난이도를 보이느냐라고 생각합니다. 보통 초기 구현
과정에서는 가장 (이해 구현이) 쉬운 알고리즘을 사용하며, 해당
알고리즘의 적용이 문제 해결의 correctness 를 보장한다는 사실을 확인한
이후에 보다 어렵지만 나은 성능을 보이는 알고리즘으로 대체하는 것이
가능합니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

bus710의 이미지

creativeidler wrote:
Z80같은 학습용 프로젝트가 아닌 바에야..

z80을 단순히 학습용으로만 여기시지는 않으시겠지요8)

life is only one time

익명 사용자의 이미지

creativeidler wrote:
Z80같은 학습용 프로젝트가 아닌 바에야..

http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=74
http://atmel.com/dyn/products/param_table.asp?family_id=607&OrderBy=1257&Direction=ASC#
마이크로칩과 아트멜은 학생들 호주머니나 털어서 먹고사는 영세한 업체입니다. PIC나 AVR은 학습용보다도 못한 애들 장난감입니다. 저딴 싸구려 칩 쓰느니 듬직한 ARM 박읍시다.
나는오리의 이미지

Anonymous wrote:
creativeidler wrote:
Z80같은 학습용 프로젝트가 아닌 바에야..

http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=74
http://atmel.com/dyn/products/param_table.asp?family_id=607&OrderBy=1257&Direction=ASC#
마이크로칩과 아트멜은 학생들 호주머니나 털어서 먹고사는 영세한 업체입니다. PIC나 AVR은 학습용보다도 못한 애들 장난감입니다. 저딴 싸구려 칩 쓰느니 듬직한 ARM 박읍시다.
하하...이글보고 저 두 회사 주식시세까지 찾아서 올리는 분 있을듯...
qualis의 이미지

creativeidler wrote:
Quote:
PC 쪽만 생각하시는것 아닌가 싶습니다.
전 얼마전에 RAM 256 Bytes 에 프로그램 메모리 1KBytes 짜리
마이컴에서 소팅이 필요했었습니다.

이런 환경에서 퀵소트의 복잡한 코드로 프로그램 메모리를 다 잡아 먹을 이유는 없죠.
버블소트가 정말로 필요한 곳도 분명 있습니다.

퀵소트도 구현하기에 따라서 10라인 정도로 구현 가능합니다. 결코 메모리를 다 잡아먹을 정도로 복잡하지 않죠.

근데 프로그램 메모리 1KB 짜리의 마이컴을 써야하는 환경인데 소팅이 필요하다? 어떤 환경인지 궁금하군요. 뭘 개발하시는 것인가요? 요즘 소팅 알고리즘을 돌릴 수 있을 정도의 프로세서를 쓰는 곳은 프로그램 메모리 1KB 이런 경우가 없는 걸로 알고 있습니다만. 거기다 메모리 256 바이트면 소팅해야할 데이터나 제대로 들어가는지가 의문이군요. Z80같은 학습용 프로젝트가 아닌 바에야..

그리고 물론 버블 소트가 퀵소트보다 빠른 경우도 있죠. 하지만 이런 경우는 어차피 전체 수행시간이 짧기 때문에 어떤 소트 알고리즘을 쓰든 별 상관 없죠. 사다리에 퀵 소트를 쓰든 버블 소트를 쓰든 별 상관 있겠습니까? 어차피 0.01초에 끝날 일이 0.0099초에 끝나든지 하는 정도의 차이겠죠.


퀵 소트는 재귀호출을 함으로서 소스에는 메모리 관련 부분이 없다하더라도, 재귀호출로 인한 스택이 계속 쌓이면서
다른 방식들에 비해서는 꽤 많은 메모리가 필요한 걸로 알고 있습니다. 재귀호출을 안 쓰는 방법이 있나요 ?

시작이 어려울 뿐이다...

cocas의 이미지

qualis wrote:
creativeidler wrote:
Quote:
PC 쪽만 생각하시는것 아닌가 싶습니다.
전 얼마전에 RAM 256 Bytes 에 프로그램 메모리 1KBytes 짜리
마이컴에서 소팅이 필요했었습니다.

이런 환경에서 퀵소트의 복잡한 코드로 프로그램 메모리를 다 잡아 먹을 이유는 없죠.
버블소트가 정말로 필요한 곳도 분명 있습니다.

퀵소트도 구현하기에 따라서 10라인 정도로 구현 가능합니다. 결코 메모리를 다 잡아먹을 정도로 복잡하지 않죠.

근데 프로그램 메모리 1KB 짜리의 마이컴을 써야하는 환경인데 소팅이 필요하다? 어떤 환경인지 궁금하군요. 뭘 개발하시는 것인가요? 요즘 소팅 알고리즘을 돌릴 수 있을 정도의 프로세서를 쓰는 곳은 프로그램 메모리 1KB 이런 경우가 없는 걸로 알고 있습니다만. 거기다 메모리 256 바이트면 소팅해야할 데이터나 제대로 들어가는지가 의문이군요. Z80같은 학습용 프로젝트가 아닌 바에야..

그리고 물론 버블 소트가 퀵소트보다 빠른 경우도 있죠. 하지만 이런 경우는 어차피 전체 수행시간이 짧기 때문에 어떤 소트 알고리즘을 쓰든 별 상관 없죠. 사다리에 퀵 소트를 쓰든 버블 소트를 쓰든 별 상관 있겠습니까? 어차피 0.01초에 끝날 일이 0.0099초에 끝나든지 하는 정도의 차이겠죠.


퀵 소트는 재귀호출을 함으로서 소스에는 메모리 관련 부분이 없다하더라도, 재귀호출로 인한 스택이 계속 쌓이면서
다른 방식들에 비해서는 꽤 많은 메모리가 필요한 걸로 알고 있습니다. 재귀호출을 안 쓰는 방법이 있나요 ?

재귀호출 안 쓰고 스택을 쓰면 됩니다. 알고리즘 수행 시간을 O(n lg n)으로 유지하면서 스택 크기는 최대 O(lg n)으로 유지할 수 있습니다. 확실히 n^2의 소트들에 비해 메모리를 좀 더 쓰긴 합니다만 얼마나 오버헤드가 걸릴지는 잘 모르겠네요. 열악한 환경에서 프로그래밍 경력이 없다보니.

qualis의 이미지

cocas wrote:
재귀호출 안 쓰고 스택을 쓰면 됩니다. 알고리즘 수행 시간을 O(n lg n)으로 유지하면서 스택 크기는 최대 O(lg n)으로 유지할 수 있습니다. 확실히 n^2의 소트들에 비해 메모리를 좀 더 쓰긴 합니다만 얼마나 오버헤드가 걸릴지는 잘 모르겠네요. 열악한 환경에서 프로그래밍 경력이 없다보니.

제가 질문을 애매하게 했나 봅니다.
재귀호출 ( 즉 스택 ) 을 안 쓰고 퀵 소트를 구현할 수 있는 방법이 있는가 하는 것이었습니다.
재귀호출을 하게 되면 당연히 스택이 쌓이게 되는 것이므로, 그 스택을 쓰지 않음으로서 메모리의 사용을 최대한
억제하는 방법이 있나 하는 것이었습니다.

저의 무지 짧은 지식으로는 불가능하다는 결론을 내린지라...

( 어떤 책에서 스택을 파일에다가 저장해서 구현을 한 경우는 봤는데.. 이런 식으로 하면 속도는 둘째치고,
메모리 상의 이점이 있는지도 궁금해집니다. )

시작이 어려울 뿐이다...

creativeidler의 이미지

퀵소트는 리턴값을 사용하는 재귀호출이 아니니까 스택을 거의 안 쓰고 구현할 수도 있을 것 같네요. 전혀 안 쓸 수는 없지만 리턴 어드레스 외의 다른 정보는 스택에 넣을 필요가 없기 때문에 스택 사용량은 함수 호출 횟수 * 1 word 정도로 제한할 수 있을 듯.

근데 스택을 파일에다 저장하는 건 좀-_- 물론 메모리 사용량은 당연히 메모리에 써야될 껄 디스크에 쓰니까 줄어들긴 하겠지만 함수 호출 한 번 할 때마다 디스크 I/O를 해야 한다면 감당이 안될 듯. 램디스크-_-라면 몰라도.

lifthrasiir의 이미지

creativeidler wrote:
퀵소트는 리턴값을 사용하는 재귀호출이 아니니까 스택을 거의 안 쓰고 구현할 수도 있을 것 같네요. 전혀 안 쓸 수는 없지만 리턴 어드레스 외의 다른 정보는 스택에 넣을 필요가 없기 때문에 스택 사용량은 함수 호출 횟수 * 1 word 정도로 제한할 수 있을 듯.

근데 스택을 파일에다 저장하는 건 좀-_- 물론 메모리 사용량은 당연히 메모리에 써야될 껄 디스크에 쓰니까 줄어들긴 하겠지만 함수 호출 한 번 할 때마다 디스크 I/O를 해야 한다면 감당이 안될 듯. 램디스크-_-라면 몰라도.

대충 O(lg n) 정도의 공간이 필요하지 않을까 싶습니다. (average case에서)

- 토끼군

cocas의 이미지

tokigun wrote:
creativeidler wrote:
퀵소트는 리턴값을 사용하는 재귀호출이 아니니까 스택을 거의 안 쓰고 구현할 수도 있을 것 같네요. 전혀 안 쓸 수는 없지만 리턴 어드레스 외의 다른 정보는 스택에 넣을 필요가 없기 때문에 스택 사용량은 함수 호출 횟수 * 1 word 정도로 제한할 수 있을 듯.

근데 스택을 파일에다 저장하는 건 좀-_- 물론 메모리 사용량은 당연히 메모리에 써야될 껄 디스크에 쓰니까 줄어들긴 하겠지만 함수 호출 한 번 할 때마다 디스크 I/O를 해야 한다면 감당이 안될 듯. 램디스크-_-라면 몰라도.

대충 O(lg n) 정도의 공간이 필요하지 않을까 싶습니다. (average case에서)

- 토끼군

흑.. 제가 위에도 썼지만 time complexity를 그대로 유지하면서 스택 요구량은 O(lg n)으로 유지할 수 있습니다. average case가 아니라 all case입니다. 저게 최악의 경우에도 성립하거든요.

creativeidler의 이미지

네, 코카스님 말씀처럼 오더는 그렇게 유지할 수 있습니다. 거기에 덧붙여 상수도 리턴 어드레스만 저장하면 되기 때문에 거의 log n * 1 word 정도로 가능하다..이런 얘기였습니다.

seoleda의 이미지

bubble sort를 하드웨어적으로 구현할 수 있다고 수업시간에 들은 적이 있습니다.

적은 개수의 원소를 하드웨어적으로 정렬하도록 하드웨어를 구성한 후, 이 하드웨어를 병렬로 연결하면 세상에서 가장 빠른 정렬 시스템을 얻을 수 있지 않을까요?

차리서의 이미지

일반적으로 버블 정렬은 퀵 정렬에 비해 코드를 작성하기 쉽다(간단하다)고 말합니다만, 구현 언어와 정렬 대상 자료구조의 특성에 따라서는 정 반대인 경우도 있습니다.

각설하고, 재귀적으로 작성된 소스 코드를 컴파일러가 자동적으로 반복문으로 바꾸어 번역하는 기법은 어느 정도 연구되어있나요? 즉, 이른바 ‘재귀 호출의 오버헤드’라는게 어느 정도나 확고부동한 것인지 궁금합니다. 제가 컴파일러 쪽에는 거의 문외한에 가까워서 잘 모르겠습니다만, 만일 특정한 형태의 재귀 호출에 한해서라도 최적의 (예를 들어 인덱스 레지스터 달랑 한두 개와 조건부 jump만 쓴다거나) 기계어 명령셋을 자동적으로 찾아주는 방법이 존재한다면 이야기가 상당히 달라지지 않을까 싶어서입니다. :roll:

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

cronex의 이미지

seoleda wrote:
bubble sort를 하드웨어적으로 구현할 수 있다고 수업시간에 들은 적이 있습니다.

적은 개수의 원소를 하드웨어적으로 정렬하도록 하드웨어를 구성한 후, 이 하드웨어를 병렬로 연결하면 세상에서 가장 빠른 정렬 시스템을 얻을 수 있지 않을까요?

이론 적인 얘기입니다. 실제 구현될 가능성은 그다지 없는 시스템입니다.
실제로 버블 정렬이 하드웨어적으로 하면 각 요소간의 비교를 한번에 한번이 아니라 모든 요소를 2개씩 짝지어서 비교할 수 있으므로 실제 속도는 O(N^2)이 아니라 O(N )이면 되지요. 문제는 정렬할 요소의 숫자만큼 하드웨어가 필요하다는 점입니다. 보통 정렬이 필요한 숫자는 적게는 1K개 부터 1M, 1G단위까지 나옵니다. 이런 만큼의 하드웨어를 만드는건 엄청난 낭비죠. 게다가 만약 1G개의 하드웨어를 구비한다쳐도 1G에서 1개만 더 많아져도 정렬을 못합니다.
결국 자료가 많아지면 많아질수록 더많은 하드웨어를 요구하므로 확장성이나 유연성 그리고 채산성에서 최악이죠.
게다가 정렬은 실제로 O(n log n)정도의 속도만으로도 충분한 성능이고 다량의 정보를 병렬로 sorting하는 방법은 bucket소트등이 있어서 굳이 저런 방법을 사용할 필요는 없습니다.
(지금 병렬 알고리즘에 대한 책이 없어서 자세한 얘기는 못해드리겠네요. 틀린 부분이 있을지도... ^^; )

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

익명 사용자의 이미지

* C언어(기타언어)를 소개할때, hello world 프로그램을 많이 사용합니다.
실제로는 .... 글쎄요.... 쓸데가 있나?
소팅을 소개할때, 버블소트를 소개하는 것도 비슷한 맥락이 아닐까요?

** 온고지신(溫故知新)/evolution 정도가 맞을 것 같습니다.

seoleda의 이미지

cronex wrote:
seoleda wrote:
bubble sort를 하드웨어적으로 구현할 수 있다고 수업시간에 들은 적이 있습니다.

적은 개수의 원소를 하드웨어적으로 정렬하도록 하드웨어를 구성한 후, 이 하드웨어를 병렬로 연결하면 세상에서 가장 빠른 정렬 시스템을 얻을 수 있지 않을까요?

이론 적인 얘기입니다. 실제 구현될 가능성은 그다지 없는 시스템입니다.
실제로 버블 정렬이 하드웨어적으로 하면 각 요소간의 비교를 한번에 한번이 아니라 모든 요소를 2개씩 짝지어서 비교할 수 있으므로 실제 속도는 O(N^2)이 아니라 O(N )이면 되지요. 문제는 정렬할 요소의 숫자만큼 하드웨어가 필요하다는 점입니다. 보통 정렬이 필요한 숫자는 적게는 1K개 부터 1M, 1G단위까지 나옵니다. 이런 만큼의 하드웨어를 만드는건 엄청난 낭비죠. 게다가 만약 1G개의 하드웨어를 구비한다쳐도 1G에서 1개만 더 많아져도 정렬을 못합니다.
결국 자료가 많아지면 많아질수록 더많은 하드웨어를 요구하므로 확장성이나 유연성 그리고 채산성에서 최악이죠.
게다가 정렬은 실제로 O(n log n)정도의 속도만으로도 충분한 성능이고 다량의 정보를 병렬로 sorting하는 방법은 bucket소트등이 있어서 굳이 저런 방법을 사용할 필요는 없습니다.
(지금 병렬 알고리즘에 대한 책이 없어서 자세한 얘기는 못해드리겠네요. 틀린 부분이 있을지도... ^^; )

저도 실제로 필요할 것이라고는 생각하지 않습니다. ^^ 다만 상상력을 조금 발휘해서, 연관메모리와 비슷하게 0x01번지를 읽으면, 가장큰 원소, 0xFF를 읽으면 가장 작은 원소를 리턴하는 하드웨어는 어떨까요? 쓸데 없을라나요? 복잡한 라우팅이나 핸드오버 프로토콜 구현시 유용하지 않을까요?
다익스트라 알고리즘이나 A* 알고리즘에서 가장 적은 원소를 찾는 부분이 오버해드가 많이 걸려서 상상좀 해봤습니다. ^^

dictions의 이미지

쉽게 생각할 수 있는 하나의 예를 들어보죠.
이미 아주 많은 데이터가 들어있는 리스트(어레이)가 있습니다.
이 리스트에 데이터를 삽입하는 연산은 아주 자주 있는 일은 아니고 종종 일어납니다.
이런 경우에 버블 소트를 사용하면 어떨까요?
리스트의 가장 끝에 새로운 아이템을 넣고 버블 소트합니다.
이런 경우에 버블 소트를 사용하면 괭장히 좋죠. 데이터가 많을수록 퀵소트나 빠르다고 알려진 알고리즘에 비해도 느리지 않을겁라 확신합니다.
물론 이 경우에 더 좋은 알고리즘도 존재할 수 있을겁니다.
뒷쪽부터 삽입하는 insertion sort가 그 예가 될수 있을지 모르겠네요.

버블소트가 느리다는 것은 보통의 경우에 결과적으로 잡(소팅)을 다 끝내놓고 보니 시간이 많이 걸렸다는 것입니다.
머신의 입장에서는 단일 연산으로 버블소트만큼 간단한 일도 없겠죠.
(개발자의 입장에서 구현한다고 생각하는 경우에도 마찬가지 생각이 들까요?)
당신의 머신이 해야 할 일은 이런 일인데 주어진 일에 대해서는 생각하지 않고 단지 사용하는 알고리즘이 버블소트라는 이유에서 짜증을 낸다면 황당할까요?
스택이나 큐만 보더라도 할 수 있는 일 자체도 극히 제한적(하는 일 자체가 별게 없으니 느리지도 않겠죠?)이지 않습니까?
그러나 사용되는곳은 너무도 많고 제역할을 잘 해주고 있습니다.
역시나 주어진 머신/툴/시간/잡(job)들을 모두 감안해서 최적의 알고리즘이라는것이 정해지는게 아닌가 하는 생각이 듭니다.
로마인의 철학이 생각나네요.
case by case.
언제나 경우에 따라 다르다는 거겠죠 ^^

cronex의 이미지

seoleda wrote:
cronex wrote:
seoleda wrote:
bubble sort를 하드웨어적으로 구현할 수 있다고 수업시간에 들은 적이 있습니다.

적은 개수의 원소를 하드웨어적으로 정렬하도록 하드웨어를 구성한 후, 이 하드웨어를 병렬로 연결하면 세상에서 가장 빠른 정렬 시스템을 얻을 수 있지 않을까요?

이론 적인 얘기입니다. 실제 구현될 가능성은 그다지 없는 시스템입니다.
실제로 버블 정렬이 하드웨어적으로 하면 각 요소간의 비교를 한번에 한번이 아니라 모든 요소를 2개씩 짝지어서 비교할 수 있으므로 실제 속도는 O(N^2)이 아니라 O(N )이면 되지요. 문제는 정렬할 요소의 숫자만큼 하드웨어가 필요하다는 점입니다. 보통 정렬이 필요한 숫자는 적게는 1K개 부터 1M, 1G단위까지 나옵니다. 이런 만큼의 하드웨어를 만드는건 엄청난 낭비죠. 게다가 만약 1G개의 하드웨어를 구비한다쳐도 1G에서 1개만 더 많아져도 정렬을 못합니다.
결국 자료가 많아지면 많아질수록 더많은 하드웨어를 요구하므로 확장성이나 유연성 그리고 채산성에서 최악이죠.
게다가 정렬은 실제로 O(n log n)정도의 속도만으로도 충분한 성능이고 다량의 정보를 병렬로 sorting하는 방법은 bucket소트등이 있어서 굳이 저런 방법을 사용할 필요는 없습니다.
(지금 병렬 알고리즘에 대한 책이 없어서 자세한 얘기는 못해드리겠네요. 틀린 부분이 있을지도... ^^; )

저도 실제로 필요할 것이라고는 생각하지 않습니다. ^^ 다만 상상력을 조금 발휘해서, 연관메모리와 비슷하게 0x01번지를 읽으면, 가장큰 원소, 0xFF를 읽으면 가장 작은 원소를 리턴하는 하드웨어는 어떨까요? 쓸데 없을라나요? 복잡한 라우팅이나 핸드오버 프로토콜 구현시 유용하지 않을까요?
다익스트라 알고리즘이나 A* 알고리즘에서 가장 적은 원소를 찾는 부분이 오버해드가 많이 걸려서 상상좀 해봤습니다. ^^


음 그런 하드웨어는 엄청나게 복잡할겁니다.
생각을 확장해가면서 설명해보자면
두개의 원소를 비교해서 작은것을 첫번째로 큰것을 두번째에 출력하는 하드웨어를 설계 했다고 봅시다.
4개 짜리 요소를 첫번째부터 소팅해서 출력할 하드웨어를 구현한다고 치면 1,2번째 , 3,4번째를 비교하고 (2개), 다시 2,4번째, 1,3번째를 다시 비교하고(2개) 다시 2,3번째를 비교(1개)해야 합니다.
4개를 정렬하는데 기존의 하드웨어 5개가 들었습니다.
요소의 갯수는 2배로 늘었는데 하드웨어는 5배로 늘었죠.
8개 일때에는
1-2, 3-4, 5-6, 7-8 (4개)를 비교하고

1-3, 2-4, 5-7, 6-8 (4개)를 비교하고

1-5, 2-6, 3-7, 4-8 (4개)를 비교하고

..... (더 이상은 복잡해서 --;; 그림을 그려가며 해야하는데 그게 힘드니...)

이 게 16개 혹은 그 이상으로 늘여가면 하드웨어가 얼마나 크고 복잡해질지.... 감이 오시는지요?

결국 하드웨어가 모든 걸 다 처리해주질 못합니다. 하드웨어가 간단하고 문제가 생길 소지가 적은 tool이기는 합니다만, hardware의 hard하다는 건 견고하다는 의미일 뿐 아니라 그만큼 유연성, 혹은 확장성이 적다는 의미도 됩니다.
그런 것을 보완해주는게 software의 존재 의의겠지요.

odd-even merge sort에 대해서 한번 알아보세요. 제가 보기엔 하드웨어를 가장 잘 이용한 소팅 알고리즘입니다.

------------------------------------------------------------
이 멍청이~! 나한테 이길 수 있다고 생각했었냐~?
광란의 귀공자 데코스 와이즈멜 님이라구~!

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.