개인적으로 가장 바보같지만 가장 인간적인 정렬 알고리즘이라 생각하는 부분이라
기대가 크다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
내가 알기로는

1. 데이터를 순서대로 쭉 스캔함
2. 스캔하다가 올바른 값을 찾으면 정렬해둠
(정렬하는 동안에는 스캔 멈춤ㅋㅋ)
3. 다시 데이터 쭉 흝음
.
.
.
반복

인 걸로 알고있다!

개념

• 배열에서 가장 작은 값을 선택하여 왼쪽부터 차례대로 배치하는 방식
• 첫 번째 패스에서 최소값을 찾아 첫 번째 위치와 교환
• 두 번째 패스에서는 두 번째 요소 이후에서 최소값을 찾아 두 번째 위치와 교환

내가 생각했던 게 맞았다!
n-1할 생각에 벌써부터 눈에서 물이 나온다!!ㅎㅎㅎ

기준 : n-1 번
각 비교 : (n-1)-1 번
-> (n-1) (n-2)...

Best Case	Average Case	Worst Case
O(n^2)	O(n^2)	O(n^2)

이거 완전 바보구만!!!

---

정렬 종류

[ 삽입 / 쉘 / 퀵 / 힙 / 병합 ]
여기서 삽입, 퀵, 병합 알고리즘은
시간 날 때 꼭 공부할 수 있도록 하기!!

 

내가 현재 아는 지식

삽입

데이터 값을 스캔함과 동시에 정렬해가는 알고리즘
(정렬하는 동안에는 스캔이 멈춤. 병렬적으로 움직이는 알고리즘은 아님)

쉘

삽입이랑 비슷하지만 스캔하는 pass..?가 여러개로 병렬적으로 움직여서 더더욱 효율적(아마)

퀵

제공된 데이터값을 반으로 나누고, 반으로 나눈 안에서 또 반으로 나누어 각각을 정렬하고 그 결과를 합치는 방식?
대표적인 문제로는 '99개의 진짜 동전과 1개의 가짜 동전 찾기'의 풀이 방법과 비슷할 것이라고 생각된다.

힙

얘는 잘 모르겠다...
퀵이랑 비슷한 것 같은데 정렬되는 순서가 반대였다...
그리고 퀵은 반반을 나누고 -> 정렬 -> 반복... -> 합침의 흐름이라면,
힙은 반반을 나누고 -> 삽입 정렬처럼 조건에 맞는 값을 두 번째 위치에 배치...하는 방식이었던 것 같다.

병합

삽입 정렬과 비슷한데,
퀵이랑 반대로 진행된다고 해야하나?

정렬하다가
-> 다음 노드가 현재 정렬된 노드들보다 더 클 때에는,
아예 다른 묶음으로 다시 정렬하고,
-> 이후에 정렬된 값들을 병합하여 정렬하고
최종본을 병합하는..? 그런 순서.

역시 내가 쓰니까 뭔 말인지 하나도 모르겠다!!
개념을 똑바로 알고 제대로 된 한국어를 구사할 수 있도록 노력해야겠다!

정렬 시간복잡도 정리표

정렬 방식	Best Case	Average Case	Worst Case	비고
버블정렬 (Bubble Sort)	O(N)	O(N^2)	O(N^2)
선택정렬 (Selection Sort)	O(N^2)	O(N^2)	O(N^2)	비교 횟수가 일정함
삽입정렬 (Insertion Sort)	O(N)	O(N^2)	O(N^2)
셸정렬 (Shell Sort)	O(N log N)	O(N log² N)	O(N^2)
퀵정렬 (Quick Sort)	O(N log N)	O(N log N)	O(N^2)	평균적으로 가장 빠름
힙정렬 (Heap Sort)	O(N log N)	O(N log N)	O(N log N)	안정적이고 일정한 성능
병합정렬 (Merge Sort)	O(N log N)	O(N log N)	O(N log N)	큰 데이터에 안정적

설명하기 가장 그지깽깽이 같았던 힙 정렬이 가장 안정적이고 일정한 성능이라니
역시 콤퓨타 고철깡통덩어리의 마음은 알다가도 모르겠다.

---

코드 구현

import java.io.*;
import java.util.*;

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputData = br.readLine().split(" ");
        int[] arr = new int[inputData.length];
        // BufferedReader 저 짱나는 놈의 로직은 보기만 해도 뇌가 깨진다!!

        for (int i = 0; i < inputData.length; i++) {
            arr[i] = Integer.parseInt(inputData[i]);
        }

        System.out.println("정렬 전 : " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("정렬 전 : " + Arrays.toString(arr));
    }
}

추가 공부

첫 번째 for문에서는 가장 작은 값이 i인 걸로 설정해둠!
현재 값(j)와 비교하기 위해 존재하는 변수!

그 다음 두 번째 for문에서 현재 위치의 값인 j를 선언하고,
j는 항상 i의 뒤(i+1)에 있도록 한다!
arr[j] < arr[minIndex]인 경우에는 j보다 더 작은 값이 등장한 거니 minIndex를 갱신하는 것.

 

int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;

이 세 줄이 살짝 헷갈리는데..

temp라는 저장소에 현재 정렬(arr[minIndex])을 넣어두고,
현재 정렬을 최종 정렬(arr[i])인 걸로 한 뒤에,
temp에 저장해둔 minIndex 값을 i 위치로 옮기고,
i 자리에 있던 값이 minIndex에 덮어씌워진다..?

자칫 오해할 수 있어 정정.

• temp에 minIndex의 값을 저장.
  이때 minIndex는 작은 값인 상태.
• i번째 자리에 작은 값(arr[minIndex])을 덮어쓰기 전에, arr[i]의 값을 [minIndex]로 옮김!

즉, 덮어씌운게 아니라 i와 minIndex의 자리를 바꾸는 로직.

이후 main 클래스에서는 터미널에 넣은 값대로 작동할 수 있는 로직이 들어가있다!
(BufferedReader+split+parsing 과정)
inputData[i] 부분은 보기만 해도 눈물이 나와서, 지금은 별로 쳐다보고 싶지 않다!