CSE/Sort
-
[Sort] 힙 정렬(Heap Sort]CSE/Sort 2015. 6. 12. 15:52
힙 정렬(Heap Sort) 정의: 힙이라는 자료구조를 이용하여 정렬하는 방법 힙은 삭제 연산을 수행하면 가장 최상위 루트원소를 반환한다. 최상위 루트원소는 힙 내부에서 가장 큰 원소이다. 힙정렬.... 힙을 이용해서 정렬을 하므로 굉장히 쉽게 사용되죠~ 왜냐면 힙 구현해 놓고 삭제 연산을 하면 정렬이 되니깐요!!! 한번 봅시다 ! 1단계 자 이렇게 최대 힙이 구성이 되어있습니다!!! 여기서 힙의 삭제연산을 합니다!! 삭제 연산은 루트 를 반환한다고 했죠??? 루트를 반환하고 힙은 다시 최대 힙을 구성합니다! 아래처럼 말이죠~ 1단계 끝!! 2단계 삭제 연산을 진행해야 겠죠??? 아래처럼 진행됩니다!! 계속 힙안에 있는 원소를 삭제 시키는 겁니다... 3단계 계속 삭제... 힙이 보잘것 없어서 아예 없어..
-
[Sort] 기수 정렬(Radix Sort)CSE/Sort 2015. 6. 12. 15:49
기수 정렬(Radix Sort) 1단계 2단계 [출처: gifsoup] 정의: 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분해하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하며 정렬함. 그림으로 보시겠습니다!!! 1단계 자 이게 첫 단계의 그림인데요~ 좀 이전의 정렬과는 다른 양상을 보이죠??? 기수 정렬은 기수를 이용한 정렬이니깐 저렇게 버킷이 존재합니다!! 1단계에서는 기수 즉, 정렬할 값들의 1의 자리를 가지고 정렬을 시도 합니다!! 음... 힌트를 드리자면, 저 위의 숫자에서 지금 단계에서 중요한건 0 1 2 6 8 9 위의 숫자들이란 겁니다!!! 버킷의 갯수를 보시면 10개 입니다. 왜냐하면 0 부터 9까지 넣겠다는 겁니다. 그래서 정렬할 숫자들의 1의 자리 수..
-
[Sort] 합병 정렬(Merge Sort)CSE/Sort 2015. 6. 12. 15:46
합병 정렬(Merge Sort) [출처: 위키] 정의: 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법 Divide & Conquer !!!! 1단계 자 위와 같이 숫자를 두고 정렬을 해봅시다!! 합병 정렬의 개념은 일단 다시 그림을 그려서 설명해야 겠네요~ 이렇게 처음에는 붙어있다고 생각하세요!! 여기서 1개의 원소집합을 갖는 부분 집합으로 쪼갭니다~ 처음엔 요렇게 2등분 했다고 보죠 다음은 분리된 걸 또 분리. 또! 분리... 각각 1개의 원소로 분리 됬네요~? 네 여기까지 분할 단계를 끝마치네요~! 2단계 이젠 다시 합쳐야 할 시간입니다!!! 합치면서 정렬됩니다!! 자 위 그림에서 등분된 집합이 다시 합쳐지는 꼴을 봅시다!! 이렇게 4개의 부분 집합으로 다시 합쳐졌죠?..
-
[Sort] 셸 정렬(Shell Sort)CSE/Sort 2015. 6. 12. 15:44
셸 정렬(Shell Sort) [출처: 위키] 정의: 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬 하는 방법 부분 집합을 만드는 기준은 원소 개수의 반으로 나누어서 반복 수행한다. 자 정의는 이정도로 하고 시작할까요?? 1단계 1단계 정렬 전입니다!! 자 먼저 부분 집합을 만들기 위해 원소 갯수 / 2 를 통해 4 라는 숫자를 만들어 둡시다. 4라는 숫자를 기준으로 부분 집합을 만들어 봅시다!! 자 이렇게 나옵니다! 4개의 부분 집합으로 보이시죠?? {69, 16}, {10, 8}, {30, 31}, {2, 22} 이렇게 색깔 별로 다르게 해서 집합을 4개 표현 했습니다!!! 집합을 하고 나면 집..
-
[Sort] 퀵 정렬(Quick sort)CSE/Sort 2015. 6. 12. 15:40
퀵 정렬(Quick Sort) [출처: 위키] 정의: 퀵정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다. 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다. 위의 정의를 잘 이해 하셔야 퀵 정렬이 쉽게 이해 됩니다!!! 1단계 위 처럼 8개의 값을 정렬 합시다!! 저기 보시면 2라는 숫자가 기준 값(Pivot)이 됬는데요... 기준 값을 구하는 법은 배열의 시작 값과 끝 값의 인덱스를 더한 것에서 2를 나눠줍니다. 즉 위에서는 ( 0 + 7 ) / 2 = > 3 이라는 인덱스 값이 나오니깐 배열의 3번째는 2라는 숫자입니다!!! ..
-
[Sort] 삽입 정렬(Insertion sort)CSE/Sort 2015. 6. 12. 15:33
삽입 정렬(Insertion Sort) [출처: 위키] 정의: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 정의는 위와 같습니다!! 그림으로 보시죠!! 정렬할 배열은 위와 같습니다. 버블버블때 썼던 놈 그대로 합죠!! 1단계: 네. 1 단계는 맨 처음 요소가 부분 집합으로 꾸려져있죠?? 그리고 10 이란 놈이 부분 집합의 놈들과 비교를 해서 들어갈 자리를 물색 합니다... 10 < 69 이므로...! 아래 처럼 정렬이 됩니다! 1단계 끝!!! 2단계: 이번엔 30을 저 안에서 비교를 하여, 30의 자리를 찾아야 합니다! 30의 자리는 딱봐도 10과 69의 사이 겠죠??? 그래서 요 단계에서는 먼저, 30 <..
-
[Sort] 버블 정렬(Bubble Sort)CSE/Sort 2015. 6. 12. 15:31
버블 정렬(Bubble Sort) [출처: 위키] 개념: 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로, 첫번째 원소부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막 자리로 정렬하게 되는 방식 개념은 일단 이렇습니다... 네... 역시 그림으로 보는게 나을듯 싶네요~ 버블버블은 너무 캡쳐뜰것이 많아서 이 포스팅은 개고생의 포문이 보이는 듯 싶네요ㅜㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 그럼 시작!! 자, 이렇게 5개의 값으로 시작하것습니다~ 1단계: 버블버블은 음... 2개씩 비교해서 큰 수를 맨 뒤로 보내는 방식입니다. 아래 그림을 통해서 1단계가 어떻게 진행되는지 보시와요 빨간 괄호 안에서 비교를 통해 어떤게 큰 수인지 찾아서 둘이 자리를 바꿉니다!! 69가 크니깐 10이랑 자리를 바꾸겠죠?? 아래처럼..
-
[Sort] 선택 정렬(Selection Sort)CSE/Sort 2015. 6. 12. 15:25
선택 정렬(Selection Sort) [출처: 위키] 개념: 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다. 전체 원소 중에서 가장 작은 원소를 찾아서 선택하고 기준 원소와 자리를 교환 하는 방식이다. 라고... 이렇게 말하면 다들 이해 안가시죠??! 그림으로 쉽게 보도록 하겠습니다! 맨 처음 정렬을 하기 위한 요런 숫자들이 있다고 칩시다. 당연히 2, 8, 10 이런 순서로 만들고 싶죠?? 근질근질 하시죠?? 자 그럼 시작해 보도록 하것습니다요~ 1단계: 맨 처음은!! 첫 원소(값)가 가장 작은 값을 찾습니다!! 아래 처럼!! 69 라는 숫자가 2 라는 가장 작은 값을 찾았네요!! 찾고 나서 자리를 바꿔 줍니다!! * 물론 2를 찾기 전에 69는 10과 30..