23/01/16 [6가지 Sort]

1일1배움/Java

23/01/16 [6가지 Sort]

kim chan jin 2023. 1. 16. 17:39

1. Selection Sort

배열 그림 순서대로 설명

첫번째 idx부터 시작(선택)해서 가장 작은 요소 찾아서 스왑

두번째 idx부터 시작(선택)해서 가장 작은 요소 찾아서 스왑

세번째 idx부터 시작(선택)해서 가장 작은 요소 찾아서 스왑

네번째 idx부터 시작(선택)해서 가장 작은 요소 찾아서 스왑

다섯번째 idx부터 시작(선택)해서 가장 작은 요소 찾아서 스왑

여섯번째 idx부터 시작(선택)해서 가장 작은 요소 찾아서 스왑

일곱번째 idx는 비교할 대상이 없으므로 정렬 종료

2. Bubble Sort

idx -1 를 기준으로 잡고 시작 (꼭 시작이 idx -1이 아니어도 됨)

idx -1 와 idx -2 를 비교해서 idx -1 이 작으면 스왑, 크면 그대로

idx -2 와 idx -3 를 비교해서 idx -2 가 작으면 스왑, 크면 그대로

idx -3 와 idx -4 를 비교해서 idx -3 이 작으면 스왑, 크면 그대로

idx -4 와 idx -5 를 비교해서 idx -4 가 작으면 스왑, 크면 그대로

idx -5 와 idx -6 를 비교해서 idx -5 가 작으면 스왑, 크면 그대로

idx -6 와 idx -7 를 비교해서 idx -6 이 작으면 스왑, 크면 그대로

idx -7 가 마지막이므로 다음 반복문으로 이동

idx -1 와 idx -2 를 비교해서 idx -1 이 작으면 스왑, 크면 그대로

idx -2 와 idx -3 를 비교해서 idx -2 가 작으면 스왑, 크면 그대로

idx -3 와 idx -4 를 비교해서 idx -3 이 작으면 스왑, 크면 그대로

idx -4 와 idx -5 를 비교해서 idx -4 가 작으면 스왑, 크면 그대로

idx -5 와 idx -6 를 비교해서 idx -5 가 작으면 스왑, 크면 그대로

idx -6 이 마지막이므로 다음 반복문으로 이동

idx -1 와 idx -2 를 비교해서 idx -1 이 작으면 스왑, 크면 그대로

idx -2 와 idx -3 를 비교해서 idx -2 가 작으면 스왑, 크면 그대로

idx -3 와 idx -4 를 비교해서 idx -3 이 작으면 스왑, 크면 그대로

idx -4 와 idx -5 를 비교해서 idx -4 가 작으면 스왑, 크면 그대로

idx -5 가 마지막이므로 다음 반복문으로 이동

idx -1 와 idx -2 를 비교해서 idx -1 이 작으면 스왑, 크면 그대로

idx -2 와 idx -3 를 비교해서 idx -2 가 작으면 스왑, 크면 그대로

idx -3 와 idx -4 를 비교해서 idx -3 이 작으면 스왑, 크면 그대로

idx -4 가 마지막이므로 다음 반복문으로 이동

idx -1 와 idx -2 를 비교해서 idx -1 이 작으면 스왑, 크면 그대로

idx -2 와 idx -3 를 비교해서 idx -2 가 작으면 스왑, 크면 그대로

idx -3 가 마지막이므로 다음 반복문으로 이동

idx -1 와 idx -2 를 비교해서 idx -1 이 작으면 스왑, 크면 그대로

idx -2 가 마지막이므로 다음 반복문으로 이동

idx -1 혼자 남았으므로 정렬 종료

3. Insertion Sort

첫번째 idx를 sorted, 두번째 idx부터 끝까지를 unsorted로 구분

unsorted 중 첫번째 요소를 sorted 요소와 비교해 알맞은 곳에 삽입

sorted.length != arr.length 이므로 계속 진행

unsorted 중 첫번째 요소를 sorted 요소들과 비교해 알맞은 곳에 삽입

sorted.length != arr.length 이므로 계속 진행

unsorted 중 첫번째 요소를 sorted 요소들과 비교해 알맞은 곳에 삽입

sorted.length != arr.length 이므로 계속 진행

unsorted 중 첫번째 요소를 sorted 요소들과 비교해 알맞은 곳에 삽입

sorted.length != arr.length 이므로 계속 진행

unsorted 중 첫번째 요소를 sorted 요소들과 비교해 알맞은 곳에 삽입

sorted.length != arr.length 이므로 계속 진행

unsorted 중 첫번째 요소를 sorted 요소들과 비교해 알맞은 곳에 삽입

sorted.length = arr.length 가 되었으므로 정렬 종료

4. Shell Sort

Shell은 배열 크기의 절반 (홀수의 경우 +1), 4

idx 0 과 idx 0으로부터 Shell 거리만큼의 idx(idx 4)를 비교하여 스왑

Shell 거리만큼의 idx(idx4)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 1 과 idx 0으로부터 Shell 거리만큼의 idx(idx 5)를 비교하여 스왑

Shell 거리만큼의 idx(idx5)가 배열 끝에 도달하지 않았으므로정렬 계속

idx 2 과 idx 0으로부터 Shell 거리만큼의 idx(idx 6)를 비교하여 스왑

Shell 거리만큼의 idx(idx5)가 배열 끝에 도달했으므로 다음 반복문으로 이동

Shell은 이전 Shell 크기의 절반, 2

idx 0 과 idx 0으로부터 Shell 거리만큼의 idx(idx 2)를 비교하여 스왑

Shell 거리만큼의 idx(idx2)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 1 과 idx 0으로부터 Shell 거리만큼의 idx(idx 3)를 비교하여 스왑

Shell 거리만큼의 idx(idx3)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 2 과 idx 0으로부터 Shell 거리만큼의 idx(idx 4)를 비교하여 스왑

Shell 거리만큼의 idx(idx4)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 3 과 idx 0으로부터 Shell 거리만큼의 idx(idx 5)를 비교하여 스왑

Shell 거리만큼의 idx(idx5)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 4 과 idx 0으로부터 Shell 거리만큼의 idx(idx 6)를 비교하여 스왑

Shell 거리만큼의 idx(idx6)가 배열 끝에 도달했으므로 다음 반복문으로 이동

Shell은 이전 Shell 크기의 절반, 1

idx 0 과 idx 0으로부터 Shell 거리만큼의 idx(idx 1)를 비교하여 스왑

Shell 거리만큼의 idx(idx1)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 1 과 idx 0으로부터 Shell 거리만큼의 idx(idx 2)를 비교하여 스왑

Shell 거리만큼의 idx(idx2)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 2 과 idx 0으로부터 Shell 거리만큼의 idx(idx 3)를 비교하여 스왑

Shell 거리만큼의 idx(idx3)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 3 과 idx 0으로부터 Shell 거리만큼의 idx(idx 4)를 비교하여 스왑

Shell 거리만큼의 idx(idx4)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 4 과 idx 0으로부터 Shell 거리만큼의 idx(idx 5)를 비교하여 스왑

Shell 거리만큼의 idx(idx5)가 배열 끝에 도달하지 않았으므로 정렬 계속

idx 5 과 idx 0으로부터 Shell 거리만큼의 idx(idx 6)를 비교하여 스왑

Shell 거리만큼의 idx(idx6)가 배열 끝에 도달했고 정렬이 완료되었으므로 정렬 종료

코드 구현까지 하려고 했는데 생각보다 너무 오래 걸림... 공사 중...

5. Quick Sort

package JAVA;

import java.util.Arrays;

public class Test {
    private static void quickSort(int[] arr,int left, int right) {
        int part = partition(arr,left,right);
        if(left<part-1) quickSort(arr,left,part-1);
        if(right>part) quickSort(arr,part,right);
    }

    private static int partition(int[] arr,int left,int right) {
        int pivot=arr[(left+right)/2];
        while(left<=right) {
            while(arr[left]<pivot) left++;
            while(arr[right]>pivot) right--;
            if(left<=right) {
                swap(arr,left,right);
                left++;
                right--;
            }
        }
        return left;
    }

    private static void swap(int[] arr,int left,int right) {
        int tmp=arr[left];
        arr[left]=arr[right];
        arr[right]=tmp;
        return;
    }

    public static void main(String[] args) {
        int[] arr= {8, 4, 6, 9, 2, 3, 1}; // arr.length=7
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}

티스토리