CSE/Sort 검색 결과

8개 발견
  1. 미리보기
    2015.06.12 - Palpit

    [Sort] 힙 정렬(Heap Sort]

  2. 미리보기
    2015.06.12 - Palpit

    [Sort] 기수 정렬(Radix Sort)

  3. 미리보기
    2015.06.12 - Palpit

    [Sort] 합병 정렬(Merge Sort)

  4. 미리보기
    2015.06.12 - Palpit

    [Sort] 셸 정렬(Shell Sort)

  5. 미리보기
    2015.06.12 - Palpit

    [Sort] 퀵 정렬(Quick sort)

  6. 미리보기
    2015.06.12 - Palpit

    [Sort] 삽입 정렬(Insertion sort)

  7. 미리보기
    2015.06.12 - Palpit

    [Sort] 버블 정렬(Bubble Sort)

  8. 미리보기
    2015.06.12 - Palpit

    [Sort] 선택 정렬(Selection Sort)

[Sort] 힙 정렬(Heap Sort]

2015.06.12 15:52 - Palpit
조회수 확인

힙 정렬(Heap Sort)






 



정의힙이라는 자료구조를 이용하여 정렬하는 방법


힙은 삭제 연산을 수행하면 가장 최상위 루트원소를 반환한다.


최상위 루트원소는 힙 내부에서 가장 큰 원소이다.





힙정렬....


힙을 이용해서 정렬을 하므로 굉장히 쉽게 사용되죠~



왜냐면 힙 구현해 놓고 삭제 연산을 하면 정렬이 되니깐요!!!



한번 봅시다 !






1단계






 



자 이렇게 최대 힙이 구성이 되어있습니다!!!


여기서 힙의 삭제연산을 합니다!!




삭제 연산은 루트 를 반환한다고 했죠???


루트를 반환하고 힙은 다시 최대 힙을 구성합니다!



아래처럼 말이죠~




 



1단계 끝!!














2단계



삭제 연산을 진행해야 겠죠???


아래처럼 진행됩니다!!




 



계속 힙안에 있는 원소를 삭제 시키는 겁니다...










3단계



계속 삭제...


힙이 보잘것 없어서 아예 없어 질때까지...




 









4단계



 










5단계





 












6단계






 












7단계












8단계




자 이렇게 마무리가 됩니다!!






 

 



이 힙 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!


모든 케이스에 대해


 


를 갖습니다!!!




자 그럼 소스 코드로 예제를 살펴 봅시다~



HeapMain.java



 

1
2
3
4
5
6
7
8
9
package Heap;
 
public class HeapMain {
    public static void main(String[] args) {
        int[] arr = { 69103021683122 };
        HeapSort.heapSort(arr);
    }
}
 
cs



HeapSort.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
package Heap;
 
import Selection.SelectionSort;
 
public class HeapSort {
    public static void heapSort(int[] arr) {
        Heap heap = new Heap();
 
        for (int i = 0; i < arr.length; i++) {
            heap.insertHeap(arr[i]);
        }
 
        for (int i = arr.length - 1; i >= 0; --i) {
            arr[i] = heap.deleteHeap();
 
        }
        System.out.println("힙 정렬 :");
        SelectionSort.printArr(arr);
    }
}
 
cs



Heap.java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
package Heap;
 
public class Heap {
    private int heapSize;
    private int itemHeap[];
 
    public Heap() {
        heapSize = 0;
        itemHeap = new int[50];
    }
 
    public void insertHeap(int item) {
        int i = ++heapSize;
 
        while ((i != 1) && (item > itemHeap[i / 2])) {
            itemHeap[i] = itemHeap[i / 2];
            i /= 2;
        }
 
        itemHeap[i] = item;
    }
 
    public int getHeapSize() {
        return this.heapSize;
    }
 
    public int deleteHeap() {
        int parent, child;
        int item, tmp;
        item = itemHeap[1];
        tmp = itemHeap[heapSize--];
        parent = 1;
        child = 2;
 
        while (child <= heapSize) {
            if ((child < heapSize) && (itemHeap[child] < itemHeap[child + 1]))
                child++;
 
            if (tmp >= itemHeap[child])
                break;
 
            itemHeap[parent] = itemHeap[child];
            parent = child;
            child *= 2;
        }
 
        itemHeap[parent] = tmp;
        return item;
    }
}
 
cs





실행 결과는 아래와 같습니다!!!


 


 


'CSE > Sort' 카테고리의 다른 글

[Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12
  • 질문 2015.06.21 18:38 신고

    힙이라는 자료구조는 자바에 내장되어 있는 건가요?
    그리고 시간 복잡도에서 log n은 자연로그인가요?
    정렬을 처음 공부하는데 너무 어렵네요ㅜㅜ

    1. BlogIcon Palpit 2015.06.22 00:13 신고

      자바에 내장되어 있지는 않습니다ㅎ
      자연로그는 아니고 그 밑이 e가 아니고 10인 로그입니다ㅎ

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 기수 정렬(Radix Sort)

2015.06.12 15:49 - Palpit
조회수 확인

기수 정렬(Radix Sort)













1단계



 


2단계


[출처: gifsoup]





정의: 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 


해당하는 버킷에 원소를 분해하였다가 



버킷의 순서대로 원소를 꺼내는 방법을 반복하며 정렬함.





그림으로 보시겠습니다!!!




1단계


















자 이게 첫 단계의 그림인데요~


좀 이전의 정렬과는 다른 양상을 보이죠???



기수 정렬은 기수​를 이용한 정렬이니깐 저렇게 버킷이 존재합니다!!





1단계에서는 기수 즉, 정렬할 값들의 1의 자리를 가지고 정렬을 시도 합니다!!


음...


힌트를 드리자면,


저 위의 숫자에서 지금 단계에서  중요한건 


0  1  2  6  8  9


위의 숫자들이란 겁니다!!!



버킷의 갯수를 보시면 10개 입니다.


왜냐하면 0 부터 9까지 넣겠다는 겁니다.


그래서 정렬할 숫자들의 1의 자리 수를 검사하는 겁니다!!!


그래서 아래처럼 버킷에 들어가게 되는 거죠!!!




 


잘 보시면 69는 버킷 9에 들어가있고

8은 버킷 8

16은 버킷 6 

이런식이죠???


이렇게 정렬 한 후, 버킷0~9까지 


순서대로


꺼냅니다!!



아래와 같이 나오게 됩니다!!







이렇게 1단계가 1의 자리수를 정렬하면서 끝이나요!!













2단계






2단계에서는 그럼 뭘하죠???



1단계에서는 1의 자리 수를 기준으로 버킷에 넣었다가 뺐습니다.




네. 이번 단계는 10의 자리 수를 기준으로 정렬합니다!!




그럼 버킷에 어떻게 들어가는지 볼까요??




 



위 처럼 들어가게 됩니다!!!




이걸 순서대로 끄집어 냅니다!!!







이렇게 나오네요~


정렬이 다되었스빈!!!!


기수 정렬 짱입니다!!




edward_special-37 







  


이 기수 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!



 



 


여기서 k는 자릿수를 말합니다!!!


정말 굉장히 빠른 녀석이죠!!!





소스 코드를 통해 보겠습니다!!!
 



RadixMain.java


 

1
2
3
4
5
6
7
8
9
10
 
package Radix;
 
public class RadixMain {
    public static void main(String[] args) {
        int[] arr = { 69103021683122 };
        RadixSort.sortLSD(arr, 2);
    }
}
 
cs



RadixSort.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
package Radix;
 
import java.util.LinkedList;
 
import Selection.SelectionSort;
 
public class RadixSort {
 
    @SuppressWarnings("unchecked")
    private static LinkedList<Integer>[] counter = new LinkedList[] {
            new LinkedList<Integer>(), new LinkedList<Integer>(),
            new LinkedList<Integer>(), new LinkedList<Integer>(),
            new LinkedList<Integer>(), new LinkedList<Integer>(),
            new LinkedList<Integer>(), new LinkedList<Integer>(),
            new LinkedList<Integer>(), new LinkedList<Integer>() };
 
    // 버킷으로 사용할 counter 변수
 
    // maxDigitSymbols는 정렬할 숫자 중에서 가장 많은 자릿수를 갖는 녀석 기준
    public static void sortLSD(int[] array, int maxDigitSymbols) {
        int mod = 10;
        int dev = 1;
        for (int i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
            for (int j = 0; j < array.length; j++) {
                int bucket = (array[j] % mod) / dev;
                counter[bucket].add(array[j]);
            }
 
            int pos = 0;
 
            for (int j = 0; j < counter.length; j++) {
                Integer value = null;
                while ((value = counter[j].poll()) != null) {
                    array[pos++] = value;
                }
 
            }
            System.out.println("기수 정렬 " + (i + 1) + " 단계:");
            SelectionSort.printArr(array);
        }
 
    }
 
}
cs



결과는 아래와 같습니다!


 


 



'CSE > Sort' 카테고리의 다른 글

[Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 합병 정렬(Merge Sort)

2015.06.12 15:46 - Palpit
조회수 확인

합병 정렬(Merge Sort)


 

 


[출처: 위키]



정의: 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법



Divide & Conquer !!!!





1단계





 



자 위와 같이 숫자를 두고 정렬을 해봅시다!!





합병 정렬의 개념은 일단 다시 그림을 그려서 설명해야 겠네요~




 


이렇게 처음에는 붙어있다고 생각하세요!!


여기서 1개의 원소집합을 갖는 부분 집합으로 쪼갭니다~




처음엔 요렇게 2등분 했다고 보죠



 





다음은 분리된 걸 또 분리.





 



또! 분리...



 


각각 1개의 원소로 분리 됬네요~?


네 여기까지 분할 단계를 끝마치네요~!












2단계



이젠 다시 합쳐야 할 시간입니다!!!


합치면서 정렬됩니다!!


자 위 그림에서 등분된 집합이 다시 합쳐지는 꼴을 봅시다!!




 


이렇게 4개의 부분 집합으로 다시 합쳐졌죠???


근데 합치면서 달라지신게 보일겁니다!!!


각 부분 집합이 정렬이 되었죠??



네. 여기가 포인트 입니다!


합쳐지면서 정렬이 이루어 집니다!





그럼 또 합쳐 봅시다!



 



자 이렇게 되었네요!!


마지막 단계만 남겨둔 상태군요...




 


이렇게 정렬이 완성이군요!!



여기서는 2-way 병합 정렬을 수행했습니다!!


2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 방식이거든요!!!


이처럼 n-way로 작성을 따로 할 수도 있습니다!!!







 


이 병합 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!


모든 케이스에 대해


 



 


를 갖습니다!!!




자 그럼 소스 코드로 예제를 살펴 봅시다~



MergeMain.java


 

1
2
3
4
5
6
7
8
9
10
package Merge;
 
public class MergeMain {
    public static void main(String[] args) {
        int[] arr = { 69103021683122 };
        MergeSort.mergeSort(arr, 0, arr.length - 1);
    }
}
 
 
cs



MergeSort.java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
package Merge;
 
import Selection.SelectionSort;
 
public class MergeSort {
    public static int[] sorted = new int[30];
 
    public static void mergeSort(int[] arr, int m, int n) {
        int middle;
        if (m < n) {
            middle = (m + n) / 2;
            mergeSort(arr, m, middle);
            mergeSort(arr, middle + 1, n);
            merge(arr, m, middle, n);
        }
    }
 
    public static void merge(int[] arr, int m, int middle, int n) {
        int i, j, k, t;
 
        i = m;
        j = middle + 1;
        k = m;
 
        while (i <= middle && j <= n) {
            if (arr[i] <= arr[j])
                sorted[k] = arr[i++];
            else
                sorted[k] = arr[j++];
            k++;
        }
 
        if (i > middle) {
            for (t = j; t <= n; t++, k++)
                sorted[k] = arr[t];
        } else {
            for (t = i; t <= middle; t++, k++)
                sorted[k] = arr[t];
        }
 
        for (t = m; t <= n; t++)
            arr[t] = sorted[t];
 
        System.out.println("\n 합병 정렬 >> ");
        SelectionSort.printArr(arr);
 
    }
}
 
cs




결과는 아래와 같습니다!!


 



 



'CSE > Sort' 카테고리의 다른 글

[Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 셸 정렬(Shell Sort)

2015.06.12 15:44 - Palpit
조회수 확인

셸 정렬(Shell Sort)






 


[출처: 위키]



정의: 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 

각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 

전체 원소들을 정렬 하는 방법



부분 집합을 만드는 기준은 원소 개수의 반으로 나누어서 반복 수행한다.



자 정의는 이정도로 하고 시작할까요??






1단계




 


1단계 정렬 전입니다!!



자 먼저 부분 집합을 만들기 위해


원소 갯수 / 2 를 통해


라는 숫자를 만들어 둡시다.


4라는 숫자를 기준으로 부분 집합을 만들어 봅시다!!



자 이렇게 나옵니다!



 


4개의 부분 집합으로 보이시죠??


{69, 16}, {10, 8}, {30, 31}, {2, 22}


이렇게 색깔 별로 다르게 해서 집합을 4개 표현 했습니다!!!



집합을 하고 나면 집합내에서 


삽입 정렬을 수행합니다!!!!




1. {69, 16}


69가 뒤로 가야 겠죠??? 


둘이 자리가 바뀌게 됩니다!!





 



2. {10, 8}

10이 더 크네요~


바뀌는게 지당하겠죠??




 


3. {30, 31}

은 변동이 없겠네요~~


그럼 Pass~


4. {2, 22}

도 마찬 가지네요~


결국 이상태로 1단계가 끝납니다!!!





 















2단계



자 그럼 아까는 부분 집합이 4였죠~?


여기에 다시 2로 나눠줍니다!


그럼 이번엔 

부분 집합의 갯수 = 2




아래 처럼 묶이겠네요~





 



그럼 그룹 

{16,30,69,31}

{8,2,10,22} 

로 나뉘어서 그룹별로 삽입정렬을 합니다!!!



삽입 정렬은 앞의 포스팅에 있으니 정렬은 아래처럼 됩니다!


먼저 첫번째 그룹만 삽입정렬!!!





 






그럼 두번째 그룹 삽입정렬!!




 


이렇게 이번 단계가 마무리 되겠네요~?


















3단계



 


자 이번에는 뭘 해야 할지 감이 오시죠??


부분 집합을 또 나눠줘야 합니다!!


그럼 이번엔 1이네요~


전체가 부분집합이 되는거니 걍 삽입 정렬 해야겠네요 ~?



삽입 정렬 하는 거기에 정렬된 결과는 아래와 같습니다~


 



자 이렇게 해서 셸 정렬이 끝입니다!!!



어떻게 보면 셸 정렬 ??


그냥 삽입 정렬 쓰는 거 아닌가?? 


할수도 있지 않나요???

a_bosss_life-21 



여기서 약간의 특혜가 있는겁니다!!


삽입 정렬은 원래! "거의 정렬" 되어 있는 경우 효율적인 특징이 있는데


그걸 이용했다고 보시면 됩니다!


 







이 셸 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!


Worst인 경우!!








Best 인 경우!!


 


Average는 


Gap에 따라 다르다!






소스 코드로 넘어가 보도록 하겠습니다!!



ShellMain.java

 

1
2
3
4
5
6
7
8
9
10
package Shell;
 
public class ShellMain {
    public static void main(String[] args) {
        int[] arr = { 69103021683122 };
 
        ShellSort.shellSort(arr);
    }
}
 
cs




ShellSort.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
package Shell;
 
import Selection.SelectionSort;
 
public class ShellSort {
    public static void intervalSort(int arr[], int begin, int end, int interval) {
        int item = 0;
        int j = 0;
 
        for (int i = begin + interval; i <= end; i = i + interval) {
            item = arr[i];
            for (j = i - interval; j >= begin && item < arr[j]; j -= interval)
                arr[j + interval] = arr[j];
            arr[j + interval] = item;
        }
    }
 
    public static void shellSort(int arr[]) {
        int interval = 0;
        int t = 1;
        int arrSize = arr.length;
 
        interval = arrSize / 2;
 
        while (interval >= 1) {
            for (int i = 0; i < interval; i++)
                intervalSort(arr, i, arrSize - 1, interval);
            System.out.println("셸 정렬 " + t++ + " 단계:  interval => " + interval);
 
            SelectionSort.printArr(arr);
 
            interval /= 2;
        }
    }
}
 
cs

 




결과는 아래와 같답니다~


 




 


'CSE > Sort' 카테고리의 다른 글

[Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 퀵 정렬(Quick sort)

2015.06.12 15:40 - Palpit
조회수 확인

퀵 정렬(Quick Sort)



[출처: 위키]




정의: 퀵정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 

먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다.

왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 

오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.



위의 정의를 잘 이해 하셔야 퀵 정렬이 쉽게 이해 됩니다!!!







1단계








 


위 처럼 8개의 값을 정렬 합시다!!


저기 보시면 2라는 숫자가 기준 값(Pivot)이 됬는데요...


기준 값을 구하는 법은 배열의 시작 값과 끝 값의 인덱스를 더한 것에서 2를 나눠줍니다.


​즉 위에서는 


( 0 + 7 ) / 2 = > 3 

이라는 인덱스 값이 나오니깐 배열의 3번째는 2라는 숫자입니다!!!




그렇게 피봇을 정하고 나면 퀵 정렬이 시작이 됩니다!!




 



위 그림처럼 L 과 R 이 퀵 정렬을 시작하기 위해 있는 변수입니다.

L과 R이 하는 일을 알아야 겠죠?!?!


L은 피봇 값보다 크거나 같은 값을 찾습니다.

R은 피봇 값보다 작은 값을 찾습니다.


1) 이 두 행위를 하는 녀석들이 둘이 같은 자리에서 만나기 전에!

값을 찾으면 둘이 swap을 해줍니다!


2) 두 L과 R이 값을 하나만 찾고 나머지가 만나게 되면 

만난 값과 피봇 값을 swap 합니다!



위 두 개념이 좀 중요해요!!! 자 그럼 시작 합니다!


시작과 동시에 L은 피봇 값보다 크거나 같은 값!을 찾았죠?? 

L은 저기서 가만히 있습니다.


그럼 R이 계속해서 움직입니다.


계속 움직여서 확인 결과 피봇 값 (2) 보다 작은 값이 없어서 


L과 만납니다!!




 


아까 L과 R이 만나면 어떻게 되죠??


2) 의 규칙을 따라서,


69와 2가 swap 되는 거죠???




 


결국 이렇게 해서 1단계가 마무리 됩니다! 아직까진 크게 정렬이 되어있진 않아요!!!













2단계



그럼 2단계를 시작하는데 다시 피봇을 정해야 합니다!!!


0 부터 6의 인덱스 이므로

3이라는 위치값이 피봇이네요!

아래와 같이 되겠네요~



 



그럼 먼저, L을 움직입니다!!

10은 피봇보다 작죠? pass

​30은 피봇보다 큽니다!!! 올치 걸려 드러부렀쓰야~


edward_special-18 



L이 30을 Hold 합니다.



 




L이 Hold 된 상태 이므로  R을 움직여서 비교해볼 차례입니다!!!


먼저, 22는 피봇보다 크므로 pass

​다음 31도 크므로 pass 


8은 피봇보다 작네요~???????


그럼 R이 8을 Hold!!




 



으잉??? L과 R이 값을 찾았네요????


1)의 규칙을 적용해서 !!!! 


L과 R의 값을 swap!!!!




 



값이 swap 되었습니다!


그러고 나서 다시 L 과 R은 만날때 까지 계속 움직입니다!



다시, L을 비교하면 8은 아까 했으니깐,


69로 넘어가서 Hold 죠??


L은 69에서 멈춤니다.



R은 피봇을 넘어 L과 만납니다.



 




결국 둘이 만났죠??


2)의 규칙!!!!!


LR의 자리와 피봇값을 swap!!!





 




으잉????

moon_mad_angry_edition-20 


L과 R의 자리만 바꾼다 하지 않았소 자네...?




그렇죠... L 과 R만 바꿨습니다 저는...


다만 좀 다음 단계를 준비하느라 이렇게 벌써 만들어 버렸네요...



이제부터 퀵 정렬의 진가!!!


Devide & Conquer를 제대로 하게 되네요!


먼저 아까 2는 정렬이 다되어서 범위 내에 빠졌으므로 녹색으로 표현


그러고 나면 보라색은 LR 값이므로 신경 쓸 필요 없습니다!



그럼 저 괄호로 표시된 2 부분 과!


피봇 값이 보이시죠???




네. 이번 단계에서 정한 피봇이 단계를 끝나면서 2개의 그룹으로 나눠 진겁니다...


무슨 말씀이신지 잘 이해 못할 거라 이해합니다...


설명을 워낙 잘 못해서리...


중요한 점은!!!


16이라는 피봇 의 왼쪽은 16보다 작은 값으로 구분 되있고!


오른쪽은 16보다 큰 값이죠???



네. 결론은 그룹핑 된 거 따로 해서 정렬을 통해 진행이 된다는 거죠!!!!



이정도로 설명하고 진행을 해보도록 하겠습니다!!!



 


다음 단계는 저기 보이는 10 과 8을 정렬합니다!!!


왜냐하면 그러하기 때문이죠....

















3단계




먼저 피봇은 아래와 같습니다!

0 + 1 / 2 = 0 이죠 결국,





 



피봇을 정하고 

L 과 R의 위치를 정해야 합니다!!


먼저, L은 피봇값과 일치하는 값이므로 Hold!


R은 피봇값보다 작은 값이므로 Hold!


두값이 swap 되겠죠???


1) 규칙으로 인해서!!!


그러면서 결국 피봇 원소를 swap 했으므로 비교를 안하게 됩니다!





 



위의 상태에서 아래상태로 해서 이번 단계를 종료하게 되는거죠!!




 



 




이 상태에서 8이 혼자 남습니다...


혼자 남게되면 정렬이고 나발이고 패스하게 되므로 이번 단계에서의


아까 나눠져있던 왼쪽 그룹핑에 대한 정렬은 마무리가 됩니다.













4단계




이번 단계는 오른쪽 그룹핑에 대한 정렬을 할 차례입니다!


피봇을 정하면 인덱스가 1인 위치가 피봇이 됩니다!


30!!




 



자 그럼 시작해 보시죠!!



L은 그냥 벌써 Hold! 가 되죠??? ( 30 보다 큰 값이니깐요.)


R도 Hold ! (30 보다 작은 값이니깐요.)



그럼 둘이 swap 해줍니다!!





 



다음으로 다시 비교를 해나가면!



L은 결국 30(피봇) 에서 멈추 겠죠???


R도 계속 움직여서 피봇에서 멈추게 됩니다! ( 왜냐하면 다 피봇보다 큰 값이니깐요.)


결국 L과 R은 Pivot 이네요??






 


이렇게 되서... 


22는 8과 같이 정렬을 할 필요가 없어지고



오른쪽의 새로운 그룹에 대해 정렬을  다음 단계에서 진행하면 끝입니다!!!









5단계







 


피봇까지 구해서 정렬을 시작할라고 봤더니 뭐... 시작해 봅시다!


L은 피봇이니깐 Hold!!


R은 69니깐 pass


그러면 L과 R과 Pivot 이죠???


31의 위치는 확정이 됩니다!




 



이렇게 해서 69가 남지만 결국 원소가 한개 이므로 끝이 납니다...


이렇게 해서 정렬이 끝났네요...



휴...


그렇죠...


삽입 버블 선택  이거와는 또 다른 


개념으로 정렬을 해서 어렵죠!!! ㅠㅠ



이해 합니다... 


그래도 이게 또 위에 들과는 다르게 좀 더 좋은 성능을 뽑아내므로 알아 두세요!!!












이 퀵 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!




Worst일 경우만 






Best와 average는




을 갖습니다!





소스 코드를 통해 보도록 하죠!!


QuickMain.java



 

1
2
3
4
5
6
7
8
9
package Quick;
 
public class QuickMain {
    public static void main(String[] args) {
        int [] arr = {69103021683122};
        QuickSort.quickSort(arr, 0, arr.length - 1);
    }
}
 
cs






QuickSort.java




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
package Quick;
 
import Selection.SelectionSort;
 
public class QuickSort {
    static int i = 0;
 
    public static void quickSort(int[] arr, int begin, int end) {
        if (begin < end) {
            int p = partition(arr, begin, end);
            quickSort(arr, begin, p - 1);
            quickSort(arr, p + 1, end);
        }
    }
 
    public static int partition(int arr[], int begin, int end) {
        int left = begin;
        int right = end;
 
        int pivot = (left + right) / 2;
 
        System.out.println("[퀵 정렬 " + ++i + "단계: pivot: " + arr[pivot]);
 
        while (left < right) {
            while ((arr[left] < arr[pivot]) && (left < right))
                // L 움직이는 부분
                left++;
            while ((arr[right] >= arr[pivot]) && (left < right))
                // R 움직이는 부분
                right--;
 
            if (left < right) {
                SelectionSort.swap(arr, left, right);
            }
        }
 
        SelectionSort.swap(arr, pivot, right);
 
        SelectionSort.printArr(arr);
 
        return left;
    }
}
 
cs






 



'CSE > Sort' 카테고리의 다른 글

[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12
[Sort] 선택 정렬(Selection Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 삽입 정렬(Insertion sort)

2015.06.12 15:33 - Palpit
조회수 확인

삽입 정렬(Insertion Sort)





 


[출처: 위키]



정의:  자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.



정의는 위와 같습니다!!




그림으로 보시죠!!



 





 


정렬할 배열은 위와 같습니다.


버블버블때 썼던 놈 그대로 합죠!!


 





1단계:



 


네. 1 단계는 맨 처음 요소가 부분 집합으로 꾸려져있죠??


그리고 10  이란 놈이 부분 집합의 놈들과 비교를 해서 들어갈 자리를 물색 합니다...



10 < 69 


이므로...!



아래 처럼 정렬이 됩니다!







1단계 끝!!!










2단계:


 


 



이번엔 30을 저 안에서 비교를 하여, 

30의 자리를 찾아야 합니다!


30의 자리는 딱봐도 10과 69의 사이 겠죠???


그래서 요 단계에서는


먼저, 

30 < 69 비교를 통해 자리를 한번 Check!


그라고나서, 10 < 30을 통해 다시 Check 하여 자기 자리를 잡게 됩니다! 아래처럼!





 


그럼 2단계 끝!!












3단계:




 


자 인제, 2를 부분 집합에서 정렬을 시켜야 합니다!



2는 딱봐도 맨앞에 들어가야 겠죠???


계속해서 비교를 통해 자기 자리를 찾는 겁니다.


69...

30...

10...


위 숫자들과 비교를 통해 자기자리를 찾는 거죠.




 



이번 단계도 끝입니다!!


















4단계:




  



16을 마지막으로 정렬 해야 합니다!!


16은 10과 30  사이에 들어가야 겠죠???








이녀석은 


결국 아래 자리에 들어가고 정렬이 끝나게 됩니다!!



 




뭔가 너무 생략된 느낌이라 죄송스럽네용...


바로 복잡도랑 코드랑 

보도록 하죠 ㅜㅜ


moon_special-20 









 




이 삽입 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!



Worst, Average





 



Best 일 경우만


 



입니다!!






그럼 소스 코드 보겠습니다!!!



InsertionMain.java

 

1
2
3
4
5
6
7
8
9
10
package Insertion;
 
public class InsertionMain {
    public static void main(String[] args) {
        int [] arr = {691030216};
        
        InsertionSort.insertionSort(arr);
    }
}
 
cs



InsertionSort.java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
package Insertion;
 
import Selection.SelectionSort;
 
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int aux = i - 1;
 
            while ((aux >= 0) && (arr[aux] > tmp)) {
                arr[aux + 1] = arr[aux];
                aux--;
            }
 
            arr[aux + 1] = tmp;
            System.out.println("삽입 정렬 " + i + "단계:");
            SelectionSort.printArr(arr);
        }
    }
}
 
cs






실행 결과 입니다.




 



이것으로 삽입 정렬 포스팅을 마치겠습니다!!


 


'CSE > Sort' 카테고리의 다른 글

[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12
[Sort] 선택 정렬(Selection Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 버블 정렬(Bubble Sort)

2015.06.12 15:31 - Palpit
조회수 확인

버블 정렬(Bubble Sort)





[출처: 위키]




개념: 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로, 

첫번째 원소부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막 자리로 정렬하게 되는 방식



개념은 일단 이렇습니다...





네... 


역시 그림으로 보는게 나을듯 싶네요~


버블버블은 너무 캡쳐뜰것이 많아서


이 포스팅은 개고생의 포문이 보이는 듯 싶네요ㅜㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ




그럼 시작!!




자, 이렇게 5개의 값으로 시작하것습니다~





1단계:




버블버블은 음...


2개씩 비교해서 큰 수를 맨 뒤로 보내는 방식입니다.


아래 그림을 통해서 1단계가 어떻게 진행되는지 보시와요





 

 


빨간 괄호 안에서 비교를 통해 어떤게 큰 수인지 찾아서 둘이 자리를 바꿉니다!!


69가 크니깐 10이랑 자리를 바꾸겠죠??



아래처럼 바뀌면서 바로 값을 또 비교하죠?? 빨간 괄호 안에서??


 



그럼 자리를 또 바꿔 줍니다.



 


또 바꿔주고... 해서 마지막 까지 왔네요


 


마지막 으로 바꿔주면!!!






빨간 괄호가 일시적으로 풀리고, 


아래와 같이 1단계가 끝이 납니다!!!




 



69라는 제일 무거운 수는 정렬 대상에서 제외 됩니다!!!














2단계:


 


자 그럼 악마의 빨간 괄호가 정렬을 위해 다시 옥죄여 오네요...




 



비교를 시작합시다!!!



오잉? 비교 해보니 30이 크니깐 가만히 있네요 10 은~


 




다음 비교로 넘어가 보니, 30 Vs 2 니깐 30이 크네용



 


바꿔 줍시다~ 그리고 비교~


 



30이 더 크므로 자리를 바꿔주면 2단계 끝이네요~~~






 



30 까지 정렬이 되었네요~















3단계:





바로 비교해보도록 하죠~






10이 더 크므로 바꿔주고 비교!






16이 더 크므로 걍 두면 


이단계는 끝이죠~





   


오호 근데 4단계까지 갈 필요가 있을까요~


운이 좋네요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ


sally_special-4 





이렇게 해서 정렬이 끝이 났네요~


 









이 버블 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!


Worst, Average




 



Best 일 경우만




입니다!!








그럼 코드로 확인해 볼까요~



먼저 BubbleMain.java 입니다

'

 

1
2
3
4
5
6
7
8
9
10
package Bubble;
 
public class BubbleMain {
    public static void main(String[] args) {
        int [] arr = {691030216};
        
        BubbleSort.bubbleSort(arr);
    }
}
 
cs






다음으로 BubbleSort.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
package Bubble;
 
import Selection.SelectionSort;
 
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int arr_size = arr.length;
 
        for (int i = arr_size - 1; i > 0; i--) {
            System.out.println("\n버블 정렬 " + (arr_size - i) + "단계");
 
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    SelectionSort.swap(arr, j, j + 1);
                }
                SelectionSort.printArr(arr);
 
            }
        }
    }
 
}
 
cs






기존 SelectionSort 때 만들었던 swap 과 printArr를 그대로 이용헀습니다.



결과는 아래와 같습니다~



 




'CSE > Sort' 카테고리의 다른 글

[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12
[Sort] 선택 정렬(Selection Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다

[Sort] 선택 정렬(Selection Sort)

2015.06.12 15:25 - Palpit
조회수 확인


선택 정렬(Selection Sort)





[출처: 위키]





개념: 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다. 
전체 원소 중에서 가장 작은 원소를 찾아서 선택하고 기준 원소와 자리를 교환 하는 방식이다.



라고... 이렇게 말하면 다들 이해 안가시죠??!



brown_special-25







그림으로 쉽게 보도록 하겠습니다!


맨 처음 정렬을 하기 위한 요런 숫자들이 있다고 칩시다.




 





당연히 2, 8, 10 이런 순서로 만들고 싶죠?? 

근질근질 하시죠??

hoppinmad_angry_line_characters-33




​자 그럼 시작해 보도록 하것습니다요~













1단계:




맨 처음은!! 첫 원소(값)가 가장 작은 값을 찾습니다!! 아래 처럼!!





69 라는 숫자가 2 라는 가장 작은 값을 찾았네요!! 

찾고 나서 자리를 바꿔 줍니다!!


* 물론 2를 찾기 전에 69는 10과 30도 비교해 봤습니다. 














1 단계(phase) 끝입니다!




2단계:




그럼 아래처럼 되어 있는 상태 입니다.





네. 여기서 저 괄호가 들어간 부분만 정렬 한다는 거죠!!!



그럼 다시 정렬을 하면!



괄호 내에서 첫 번째 원소(값) 10 8이라는 가장 작은 숫자를 찾았네요!







두 값을 바꿔줍니다!!





















여기까지 2 단계(phase) 끝입니다! 



3단계:




2 단계까지 끝난 상태는 아래와 같습니다!!






점점 정렬할 부분이 줄어들고 있죠~?



계속 진행해 보도록 핪!!!!




괄호 내의 첫 원소 30이 가장 작은 값인 10을 찾았네요~!








두 값의 위치를 바꿔줍니다!!




 







여기까지 3 단계(phase) 끝입니다! 


 

점점 캡쳐뜨는데 힘이 부치지만 힘내서 마무리 짓도록 하겠습니다!!

hoppinmad_angry_line_characters-37





4단계:



3단계가 끝난 상태는 아래와 같습니다!




 



인자 3개의 원소만 정렬해주면 됩니다!!!


방법은 첫 원소가!!! 가장 작은 값이랑 자리를 바꾸는 방식!!




해서! 69라는 값이 16과 자리를 바꿉니다!!


before:


 



after:



 






여기까지 4 단계(phase) 끝입니다!







5단계:



4 단계까지 끝나면 아래와 같아요~





인제 뭐 2갠데 걍 바꾸면 정렬 완료겠죠?~?





  


위의 요걸 아래처럼 바꾸면 정렬 끝 !!!



 












이렇게 해서 정렬이 끝났습니다...
hoppinmad_angry_line_characters-2




이 선택 정렬(Selection Sort)의 시간 복잡도(Time Complexity)는 아래와 같습니다!

Best, Worst, Average 모두다




입니다...


왜 냐 면





이니까요...

복잡도 계산은 왜 그런지 보다는 여러분은 Best와 Worst 정도가 빅오표기법으로 어떻게 되느냐 
정도만 아시면 되니깐 부연설명은 안하겠습니다...






그럼 코드를 한번 봅시다요!

Java로 짜봤습니다~

SelectionMain.java와 SelectionSort.java로 나눴습니다.

먼저, SelectionMain.java

1
2
3
4
5
6
7
8
9
10
package Selection;
 
public class SelectionMain {
    public static void main(String[] args) {
        int [] arr = {6910302168}; // 정렬 전 배열
        
        SelectionSort.selectionSort(arr);
    }
}
 
cs






 
여기에 아까 정렬 전의 숫자가 그대로 있죠???


다음은 SelectionSort.java


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
package Selection;
 
 
public class SelectionSort {
    public static void selectionSort(int [] arr) {
        int min = 0// 최저 값을 담을 요소
        
        for (int i = 0; i < arr.length - 1; i++) {
            min = i; // 첫번째 요소를 선택
            
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) // 첫번째 요소와 가장 적은 값을 찾는 비교 연산 
                    min = j;
            }
            swap(arr, min, i); 
            System.out.println("선택 정렬 " + (i + 1) + " 단계: ");
            printArr(arr);
        }
    }
    
    public static void swap(int [] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    public static void printArr(int [] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
 
cs







이렇게 작성 후, 실행한 결과 아래와 같아요~





'CSE > Sort' 카테고리의 다른 글

[Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
[Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
[Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
[Sort] 퀵 정렬(Quick sort)  (0) 2015.06.12
[Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
[Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12
[Sort] 선택 정렬(Selection Sort)  (0) 2015.06.12

다른 카테고리의 글 목록

CSE/Sort 카테고리의 포스트를 톺아봅니다