[크래프톤 정글] day 5 TIL 정렬(정렬, 버블정렬,선택정렬, 삽입정렬)

• BOJ (백준온라인저지) 작동원리
  • 입력과 출력을 번갈아서 해도 된다.
  • 근본적으로 입,출력 파일이 분리
  • 시간 제한은 각 파일마다 분리
• 좋은 코드란?
  • 정답을 내는 코드
  • 계산 복잡도가 낮은 코드
  • 사람이 알아보기 좋은 코드
    • 코드와 변수명이 짧다.
      • 정렬 알고리즘
        • 데이터를 정렬하는 이유
          • 탐색을 위해, 데이터베이스 같은 경우 이론상 무한개의 데이터를 다룬다.
          • 즉, 컴퓨터에서 정렬을 수행하는 이유 중 가장 큰 이유는 이진탐색이 가능한 데이터를 만들기 위해서 이다.
        • 정렬이 되어 있지 않는 경우
          • 순차 탐색 이외에 다른 알고리즘 사용 x
        • 정렬이 되어 있는 경우 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다.
          • 이진 탐색이란? 최악의 경우에도 (log N의 성능) 32회
            • 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘.
            • 찾는 값보다 크면 뒤쪽 반을 잘라버리고, 작으면 앞쪽 절반을 잘라버림.
            • 1~100에서 77를 찾을 때
              • 찾는 숫자가 50인가 ? yes retrun
          • 순차 탐색이란?
            • 말 그대로 하나씩 찾아보는 과정
        • 대게 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다.
          • 1만개를 1초에 정렬하면 10만개는 100초
        • 안정 정렬과 불안정 정렬
          • 안정 정렬
            • 중복된 값을 입력 순서와 동일하게 정렬.
            • 병합 정렬, 버블 정렬
          • 불안정 정렬
            • 뒤섞이는 것.
            • 퀵 정렬
          • 안정 정렬과 불안정 정렬 예제
        • 정렬의 종류
          • O(n^2)인것 (런타임 정수 6만개 → 22.894sec)
            • 버블 정렬
              • 서로 인접한 두 원소를 검사하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
              • 1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째,…, n-1번째와 n 번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2와 n-1번째 까지 해서 최대 n(n-1)/2 번 정렬한다.
              • 한번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것 처럼 보여 거품 정렬
              • 거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다.
                • 이미 정렬된 자료에서 왜 정렬을?
                  • 정렬 알고리즘은 자료가 정렬되어 있는 지 아닌지는 모르고 작동하기 때문에 의미가 있다.
              • 알고리즘적 관점에서 대단히 비효율적인 정렬 방식.
                • 근데 왜 배우냐?
                  • ‘수학적 직관이 없는 컴퓨터가 정렬이라는 개념을 어떻게 적용하는 지’ 배우면서 컴퓨터에 대한 이해를 쌓는 과정으로서 의의. 왜 비효율적인지 이해하는 것 역시 중요
                    • 왜 비효율적인가?
                      • 이미 정렬되어 있는 수도 비교를 진행.
              • 버블 정렬에서 파생된 칵테일 정렬
                • 순회 방향의 차이만 있다.
              • 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훓어서 가장 작은 게 2번째……해서 (n-1)번 반복한다.
              • 파생형으로 이중 선택 정렬
                • 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고 최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여 반복하는 방식
            • 삽입 정렬
              • k번째 원소를 1부터 k-1번째까지와 비교해 적절한 위치에 끼워 넣고, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식.
                • 한 칸씩 뒤로 밀어내는 방식.

• 참고한 블로그
  • https://namu.wiki/w/정렬 알고리즘#s-4.1.1
  • https://hsp1116.tistory.com/33
  • https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
  • https://kimdohyeon.tistory.com/32