kingsubin

void selectionSort(int[] arr) {

    int indexMin, temp;
    
    for (int i = 0; i < arr.length-1; i++) {
    	indexMin = i;
        for (int j = i+1; j < arr.length; j++) {
        	if (arr[j] < arr[indexMin]) {
            	indexMin = j;
            }
        }
        
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
	}
    System.out.println(Arrays.toString(arr));

}

 

1. 선택 정렬 (Selection Sort)

- 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것

1) 주어진 배열 중에서 최소값을 찾는다.

2) 그 값을 맨 앞에 위치한 값과 교체한다.

3) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

- 시간 복잡도 : O (n^2)

- 공간 복잡도 : O (n)

 

- 장점 

 버블정렬과 마찬가지로 단순하다.

 많은 교환이 일어나야 하는 자료상태에서는 비교적 효율적

 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

 

- 단점

 시간 복잡도가 O(n^2)이므로 비효율적

 불안정 정렬 (Unstable Sort)이다.

 

---

 

 

void bubbleSort(int[] arr) {
    int temp = 0;
    
    for (int i = 0; i < arr.length; i++) {
    	for (int j = 1; j < arr.length-i; j++) {
        	if (arr[j-1] > arr[j]) {
            	temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    
    System.out.println(Arrays.toString(arr));
}

 

2. 버블 정렬 (Bubble Sort)

- 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다.

1) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소와, .... 이런식으로 (마지막-1)번째 원소와 마지막 원소를

  비교하여 조건에 맞지 않는다면 서로 교환한다.

2) 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소를 정렬에서 제외,

  2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외.

  이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

- 시간복잡도 : O (n^2)

- 공간복잡도 : O (n)

 

- 장점

 구현이 매우 간단하고, 소스코드가 직관적

 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지않는다.

 안정 정렬 (stable Sort) 이다.

 

- 단점

 시간복잡도가 최악, 최선, 평균 모두 O (n^2)이므로, 비효율적이다.

 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환연산이 많이 일어난다.

 

---

 

void insertionSort(int[] arr) {
    
    for (int index = 1; index < arr.length; index++) {
    	int temp = arr[index];
        int prev = index - 1;
        
        while ( (prev >= 0) && (arr[prev] > temp) ) {
            arr[prev+1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

 

3. 삽입 정렬 (Insertion Sort)

- 각 숫자를 적절한 위치에 삽입한다. 

- 거의 정렬된 상태라면 효율적이다.

1) 정렬은 2번째 위치의 값을 temp에 저장한다.

2) temp와 이전에 있는 원소들과 비교하며 삽입해나간다.

3) '1'번으로 돌아가 다음 위치의 값을 temp에 저장하고, 반복한다.

 

=> 그 회차의 인덱스의 값의 자리를 찾아간다라고 생각

 

- 시간복잡도 : 최선의 경우 : O (n), 최악의 경우 O (n^2)

- 공간복잡도 : O(n)

 

- 장점

 알고리즘이 단순하다.

 대부분의 원소가 이미 정렬된 상태라면, 매우 효율적이다.

 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

 안정 정렬 (Stable Sort)이다.

 Selection Sort나 Bubble Sort와 같은 O (n^2) 알고리즘에 비교하여 상대적으로 빠르다.

 

- 단점

 평균과 최악의 시간복잡도가 O (n^2)이므로 비효율적이다.

 Bubble Sort, Selectino Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적

 

---

 

public void quickSort(int[] arr, int left, int right) {
	
    if (left >= right) return;
    int pi = partition();
    
    quickSort(arr, left, pi - 1);
    quickSort(arr, pi + 1, right);
}

public int partition(int[] arr, int left, int right) {
	
    int pivot = arr[left];
    int i = left;
    int j = right;
    
    while (i < j) {
    	while (pivot < arr[j]) {
        	j--;
        }
        while (i < j && pivot >= arr[i]) {
        	i++;
        }
        swap(arr, i, j);
    }
    
    arr[left] = arr[i];
    arr[i] = pivot;
    
    return i;
}

(1) 퀵 정렬 구현 1

void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;
    
    int pivot = start;
    int i = start + 1;
    int j = end;
    int temp;
    
    while (i <= j) { // 엇갈릴 때까지
    	while (i <= end && arr[i] <= arr[pivot] ) { // 피봇값 보다 큰 값 만날때 까지
        	i++;
        }
        while (j > start && arr[j] >= arr[pivot] ) { // 피봇값 보다 작은 값 만날때 까지
        	j--;
        }
        
        if (i > j) { // 엇갈린 상태면 피봇값과 교체
            temp = arr[j];
            arr[j] = arr[pivot];
            arr[pivot] = temp;
        } else { // 엇갈리지 않았다면 i j 교체
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        
    }
    
    quickSort(arr, start, j - 1);
    quickSort(arr, j + 1, end)
   
   
}

(2) 퀵 정렬 구현 2

 

public int partition(int[] arr, int left, int right) {
	int mid = (left + right) / 2;
    swap (arr, left, mid);
    ...
}

/**
*	퀵소트 O (n^2) 해결 방법
*	피벗을 선택할 때 중간요소로 선택시 해결 가능
*/

(3) 퀵 정렬의 O (n^2) 해결 방법

 

 

4. 퀵 정렬 (Quick Sort)

- 대표적인 분할정복 알고리즘

- 피벗값을 잡고 왼쪽 오른쪽 분할해서 수행

 

1) 피벗 선택

2) 오른쪽(j) 에서 왼쪽으로 가면서 피벗보다 작은 수 찾음

3) 왼쪽(i) 에서 오른쪽으로 가면서 피벗보다 큰 수 찾음

4) 각 인덱스 i,j 에 대한 요소를 교환

5) 2,3,4 과정 반복

6) 더 이상 2,3 과정 진행이 불가능하면, 현재 피벗과 교환 : 엇갈렸을때

7) 이제 교환된 피벗 기준으로 왼쪽엔 피벗보다 작은 값, 오른쪽엔 큰 값들만 존재함

 

- 시간복잡도 : 평균 O (n * logN) , 최악 (O^2)

 

---

 

void mergeSort (int[] arr, int left, int right) { // 쪼개기
	
    if (left < right) {
    	int mid = (left + right) / 2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge (int[] arr, int left, int mid, int right) { // 합치기
    int[] L = Arrays.copyOfRange(arr, left, mid + 1);
    int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);
    
    int i = 0;
    int j = 0;
    int k = left;
    int ll = L.length;
    int rl = R.length;
    
    while (i < ll && j < rl) {
    	if (L[i] <= R[j]) {
            arr[k] = L[i++];
        } else {
            arr[k] = R[j++];
        }
    	k++;
    }
    
    // remain
    while (i < ll) {
    	arr[k++] = L[i++];
    } 
    while (j < rl) {
    	arr[k++] = R[j++];
    }
}

 

 

5. 병합 정렬 (Merge Sort)

- 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현

- 빠른 정렬로 분류되며, 퀵 정렬와 함께 많이 언급되는 정렬 방식

 

* 분할정복 ?

-> 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식

 

- 시간복잡도 : 평균,최선,최악 모두 O (n * logN)

 

- 퀵 정렬과의 차이점

퀵정렬 : 우선 피벗을 통해 정렬 (partition) -> 영역을 쪼갬 (quickSort)

병합정렬 : 영역을 쪼갤 수 있을만큼 쪼갬 (mergeSort) -> 정렬 (merge)

 

 

---

    public static void main(String[] args) {
        int[] array = { 230, 10, 60, 550, 40, 220, 20 };

        heapSort(array);

        for (int v : array) {
            System.out.println(v);
        }
    }

    // 힙 정렬 전체
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // max heap 초기화
        for (int i = n/2-1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // extract 연산
        for (int i = n-1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    // 최대 힙을 구하는 메소드
    public static void heapify(int[] arr, int n, int i) {
        int p = i;
        int l = i * 2 + 1;
        int r = i * 2 + 2;

        // 왼쪽 자식 노드
        if (l < n && arr[p] < arr[l]) { // 부모 노드와 왼쪽 자식 노드 비교
            p = l;
        }
        // 오른쪽 자식 노드
        if (r < n && arr[p] < arr[r]) {
            p = r;
        }

        // 부모 노드 < 자식 노드
        if (i != p) {
            swap(arr, p, i);
            heapify(arr, n, p);
        }
    }

    // 자리 바꾸기
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

 

6. 힙 정렬 (Heap Sort)

- 완전 이진 트리를 기본으로 하는 Heap 자료구조를 기반으로한 정렬 방식 

 

- 순서

 

1) 최대 힙을 구성

2) 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임

3) 힙의 사이즈가 1보다 크면 위 과정 반복

 

힙 정렬을 수행하기 위해서는 힙 생성 알고리즘 (Heapify Algorithm)을 사용한다.

힙 생성 알고리즘은 특정한 '하나의 노드' 에 대해서 수행하는 것이다.

또한 해당 '하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태'라고 가정한다.

 

힙 생성 알고리즘 (Heapify Algorithm)은 특정한 노드의 두 자식 중에서 더 큰 자식과 

자신의 위치를 바꾸는 알고리즘이다.

또한 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우 또 자식 중에서 더 큰 자식과 자신의

위치를 바꾸어야 한다. 자식이 더 이상 존재하지 않을 때 까지.

 

 

- 시간 복잡도 : 평균,최선,최악 모두 O (n * logN)

 

* 트리 ?

-> 말 그대로 가지를 뻗어나가는 것처럼 데이터가 서로 연결되어있다는 것

 

* 이진 트리 ?

-> 모든 노드의 자식 노드가 2개 이하인 트리 구조

 

* 완전 이진 트리 ?

-> 데이터가 루트(Root) 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로

   차근차근 들어가는 구조의 이진 트리

-> 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 가득 찬 구조

 

* 힙 ?

-> 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

-> 최대힙, 최소힙 존재. 

    최대 힙은 '부모 노드'가 '자식 노드'보다 큰 힙

 

- 힙 정렬이 유용할 때 

-> 가장 크거나 가장 작은 값을 구할 때 

     최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능

-> 최대 k 만큼 떨어진 요소들을 정렬할 때

    삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있음 

 

---

int[] count = new int[5]; // 최댓값이 5일때
int[] arr = { ... }; 

for (int i = 0; i < arr.length; i++) {
    count[arr[i] - 1]++;
}

for (int i = 0; i < 5; i++) {
    if (count[i] != 0) {
    	for (int j = 0; j < count[i]; j++) {
            System.out.print( (i + 1) + " ");
        }
    }
}

 

8. 계수 정렬 (Count Sort)

- 크기를 기준으로 갯수를 센다.

- '범위 조건' 이 있는 경우에 한해서 굉장히 빠르다.

- Counting이 필요 : 각 숫자가 몇 번 등장했는지 센다.

 

- 시간 복잡도 : O (n)

- 공간 복잡도 : O (k) -> k만큼의 배열을 만들어야 함.

 

- 단점 

  배열 사이즈 N 만큼 돌 때, 증가시켜주는 Counting 배열의 크기가 큼. (메모리 낭비가 심함)

 

 

 

---

※참조

github.com/gyoogle/tech-interview-for-developer

blog.naver.com/ndb796/221226794899