EzDoum

찾기
처음으로 | 찾기 | 아카이브 | 글 올리기 | 링크 | 자료실 | 통계 | 연락처 | 자유게시판
이지도움 특집
전체보기
네트워크
TI OMAP35x
TI DaVinci
Analog Blackfin
RobotWar2005
임베디드!
캐쉬의 모든것
메모리 할당 알고리즘
CPU 파이프라이닝
자료구조(Tree)
금융

Login
이름

암호

기억하기


사용자 등록

현재 접속중인 등록 사용자는 0명, 익명 사용자는 3명 입니다.
전체 등록 사용자: 751명

마지막 답장
·libcurl + fuse 조합으로 되는게 많네. (1)
·Linux Ftrace에 관해 (3)
·Android MTP ( Media Transfer Protocol ) (1)
·Lighttpd에 인증을 digest 사용시 IE 오동작 문제? (1)
·Dtrace에 관해 (1)

최근글
·OpenSSL and multi-threads (0)
·ARM 환경에서 OpenCL 사용 (0)
·IoT용 WIFI 모듈 비교 ( MCU ) 클래스 (0)
·Glances - 리눅스 여러 가지 항목을 한 화면에서 모니터링 (0)
·plugin 방식의 로그 분석기 (0)

뜨거운 감자
·나는 인터렉티브한 환경에서 역어셈블 한다. (12)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)
·ASP.NET의 데이터 그리드와 사용자 컨트롤 (7)
·DHTML Editing Control (7)

가장 많이 읽은 글
·[Cache] 2-way Set-Associative 방식이란 무엇일까? (2)
·멀티쓰레드(Pthread) 프로그래밍
·Sorting Algorithm Animation (2)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·ReverseEngineering - 종합선물세트 (2)

Sorting Algorithm Animation
글쓴이: EzDoum 글쓴날: 2002년 07월 16일 오후 09:05




DATA를 정렬하는 방법에는 여러가지가 있다.

* Insertion Sort
* Selection Sort
* Bubble Sort
* Quick Sort
* Merge Sort
* Heap Sort

애니메이션 보기 : http://math.hws.edu/TMCM/java/xSortLab (추천)

Bubble Sort, Insertion Sort, Selection Sort는 크기가 작은 list를 제외하고는 비효율적이고, 그에 반해 Merge Sort, Quick Sort는 좀 더 복잡하긴 하나 크기가 큰 list의 경우에 대해서는 빠르다.
평균적으로 Quick Sort가 가장 빠르고, Bubble Sort가 가장 느리다.

● Bubble Sort
기본 동작은 이웃하는 item을 비교하는 것으로, 만약에 두 item이 sorting되어 있지 않다면 그 item들을 swapping한다. comparing과 swapping을 통해 움직인다. 가장 큰 item이 제일 마지막 위치로 bubble up되고 다음 큰 item이 그 다음 위치로, 이런 동작이 계속해서 반복된다. 즉, 각 phase에서 한 item이 리스트의 끝에서 마지막 위치로 이동하는 것이 중요한 동작이다.

● Selection Sort
Sorting 방법 중 이해가 가장 쉬운 방법이다. 각 phase에서 다음으로 가장 큰 item을 찾고 리스트의 끝으로 이동한다. 동시에 두 개의 item을 비교한다. 리스트에서 가장 큰 item을 찾기위해 한 item을 리스트에 남은 item들과 하나씩 비교하면서 가장 큰 item을 찾아낸다.

● Insertion Sort
기본 동작은 정렬된 리스트를 얻기 위해 리스트에서 적당한 위치에 새로운 item을 삽입하는 것이다. 매 시간마다 새로운 item이 삽입되면서 정렬된 리스트의 길이가 길어진다. 남아 있는 item을 한번에 하나씩 삽입할 수 있다. 문제는 새로운 item이 리스트에 삽입되는 위치를 결정하는 것이다.

● Merge Sort
두 개의 정렬된 리스트를 하나의 정렬된 리스트로 merging하는 idea를 이용한다. 첫 phase에서 1 length의 list를 merging시켜 2 length의 list로 다음 phase에서 2 length의 list를 4 length의 list로 그리고 나서 4 length를 8 length로 merging 시키는 과정을 하나의 긴 정렬된 리스트가 될 때까지 계속해서 반복한다.

● Quick Sort
Sorting 방법 중 가장 복잡하다. 중요 동작은 리스트로부터 한 item을 제거하고 나머지 item들을 제거된 item보다 큰 쪽과 작은 쪽으로 나누어 리스트를 두 부분으로 분리한다. 더 작은 item들을 리스트의 앞 부분으로 더 큰 item들을 리스트의 끝 부분으로 이동시킨다. 가운데 부분에 gap을 남기고, 시작 부분에서 제거된 item은 gap에 놓여지고 gap을 중심으로 더 작은 것은 왼쪽에 더 큰 것은 오른쪽에 위치한다. gap에 놓여진 item은 정확한 최종 위치가 된다. 각 부분에서 이러한 과정을 recursive하게 동작하면서 sorting이 완료된다.

http://www.ezdoum.com/upload/3/20020716232733/tmcm-java-labs.zip


  • 관련 링크
  • [분류: C/C++ 인쇄용 페이지 본문 email로 보내기 ]

    <  Labs and Applets for The Most Complex Machine | GDB Internals  >
    Sorting Algorithm Animation | 답장: 2개 | 본문에 답장
    정렬 :  
    답장 EzDoum 2002년 07월 20일 오후 12:31 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
    각 정렬 알고리즘을 수행하는 동안 메모리를 참조하는 패턴을 분석할수 있는 애플릿이 있어서 링크 걸어 둡니다.

    이 패턴이 왜 중요하냐면, 정렬 알고리즘 중에 비교횟수나 교환횟수가 많더라도 CPU캐쉬 적중률이 높다면, 전체적으로는 더 효율적인 알고리즘이 되기 때문입니다.

    일딴 링크해두고 이 호기심에 대한 결론(CPU캐쉬 친화적인 정렬 알고리즘은 어떤것이지?)은 차후에 올리도록 하지요~;

    http://cs.smith.edu/~thiebaut/java/sort/demo.html

    # 캐쉬 친화적인 프로그래밍
    http://www.ezdoum.com/stories.php?story=02/05/06/5770656

    # 캐쉬의 모든것
    http://www.ezdoum.com/search.php?query=%5Bcache%5D
    --
    걀걀걀...


    [수정]

    답장 EzDoum 2002년 08월 22일 오전 01:22 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
    http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

    Bubble Sort
    Bi-Directional Bubble Sort
    Selection Sort
    Shaker Sort
    Insertion Sort
    In-Place Merge Sort
    Double Storage Merge Sort
    Comb Sort 11
    Shell Sort
    Heap Sort
    Quick Sort
    Quick Sort with Bubble sort
    Enhanced Quick Sort
    Fast Quick Sort
    Radix Sort Algorithm
    [수정]

    Sorting Algorithm Animation | 답장: 2개 | 본문에 답장
    정렬 :  

    답장 쓰기
    글을 올리시려면 로그인 (사용자 등록) 하셔야 합니다.

    검색
    Google

    분류
    ·공지 (6)
    ·인터넷 (87)
    ·하드웨어 (260)
    ·C/C++ (65)
    ·어셈블리 (7)
    ·리눅스 (136)
    ·리눅스 커널 (67)
    ·윈도우즈 (25)
    ·데이터베이스 (20)
    ·보안 (16)
    ·.NET (25)
    ·그래픽 (13)
    ·책소개 (42)
    ·호기심 천국 (80)
    ·잡담 (111)
    ·사랑 (3)

    전체 본문수: 963
    전체 답장수: 525


    분류 : C/C++
    최근글
    최근글
    가장 많이 읽은 글
    ·Sorting Algorithm Animation (2)
    뜨거운 감자
    ·눈으로 보는 자료구조 (5)

    EzDoum투표
    이지도움 어때요?
    이게 뭐야. 다시 안올란다. --;
    아이 좋아라~ +_+;
    관심없다.
    먼가는 있는거 같은데 뭐하는 곳이지?
    기타 (자유게시판에 글로 남겨 주세요)
    [ 결과 | 투표 ]

    랜덤 링크
    http://kldp.net


     Home ^ BACK TO TOP ^ EzDoum - 도움이 필요하세요~??
     Powered by KorWeblog 1.5.8 Copyleft © 2001 EzDoum, 관리자: EzDoum