• 알고리즘의 시작은 다양한 정렬 알고리즘을 공부하는 것부터 시작이 된다.
• 알고리즘을 연습할땐 유명한 알고리즘을 따라 해보면서 알고리즘을 이해하고 스스로 만들어봐야 한다.
• 알고리즘 연습 방법
  • 문제를 읽고 분석한 후 간단한 경우부터 복잡한 경우 순서대로 생각해보면서 알고리즘을 생각해 본다. (직접 작성해가면서 생각해봐도 좋다.)
  • 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
  • 코드화하기 위해서 데이터 구조 또는 사용할 변수를 정리하고 각 문장을 코드 레벨로 적는다.

정렬이란?

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것이다.
• 정렬은 프로그램 작성 시 빈번하게 필요로 한다.

버블 정렬 이란?

• 두 인접한 데이터를 비교해 원하는 순서에 따라 swap 하고, 데이터의 전체 값이 원하는 순서로 정렬이 될 때까지 반복한다. (2개의 데이터를 계속 비교해가며 인덱스를 교환한다.)
  • [1,2] 일때 원하는 정렬 방식이 내림차순이라면 1과 2의 위치를 스왑 한다.
  • [3,6,1,2] 일 때 처음부터 두 데이터씩 값을 비교해 내림차순이라면
    • 3과 6을 비교해 6을 앞으로 보낸다.
    • 바뀌어진 3과 1을 비교해 순서가 맞다면 내버려둔다.
    • 1과 2를 비교해 2를 앞으로 보낸다.
    • 이렇게 스왑 한다면 [6,3,2,1] 내림차순으로 정렬이 된다.
    • 하나의 배열에 버블정렬을 적용한다면, 최대 배열의 사이즈 -1번의 정렬이 필요하다.
      • 로직이 한번 적용이 될 때마다, 맨 뒤의 데이터가 원하는 순서의 값이 오게 된다. (내림차순이라면 가장 작은 값, 오름차순이라면 가장 큰 값)
      • 이중 반복문으로 사이즈-1의 상수회를 반복하는 반복문 안에 앞 데이터와 뒷 데이터의 값을 비교해 swap을 한다.
      • 불필요한 체크를 피하기 위해 boolean 변수를 선언해 이미 정렬이 다 되었다면 break 해준다.
      • 따라서 버블정렬은 O(n^2)의 시간복잡도를 가진다. (완전 정렬이 되어있는 상태라면 O(n)이 된다.)

선택 정렬 이란?

• 모든 데이터를 순회하면서 원하는 순서(가장 작거나 크거나) 별로 값을 선택해서 맨 앞 인덱스로 swap 한다.
  • 가장 작거나 큰 데이터를 기억하고 있다가 모든 순회가 끝난다면 앞으로 스왑 한다.
  • 마찬가지로 두 번째로 작거나 큰 데이터를 기억하고 있다가 맨 앞+1으로 스왑 한다.
  • 이런 식으로 마찬가지로 크게는 n개의 데이터가 있다면 n-1번 반복을 한다.
    • 맨 처음에는 맨 앞 인덱스를 저장한 후, 해당 인덱스 +1부터 순회를 하면서 값을 비교한다.
    • 반복문을 다 끝낸 후, 저장된 인덱스와 맨 앞 인덱스를 스왑 하는 식으로 정렬을 진행한다.
  • 마찬가지로 n번 반복하는 반복문이 2개 이므로 O(n^2)의 시간복잡도를 가진다.

삽입 정렬 이란?

• (오름차순 기준) 데이터를 처음 인덱스부터 순회하면서 해당 인덱스의 데이터보다 앞의 인덱스의 데이터가 값이 크다면 스왑하는 식으로 앞의 인덱스의 값과 비교하며 스왑 하여 작은 데이터가 앞에 존재할 때 멈춘다.
  • 맨 앞의 인덱스 +1 부터 앞의 값과 비교를 한다.
    • 안에 속해있는 반복문은 밖의 반복문 +1 부터 맨앞의 인덱스까지 순회한다.
      • 어떻게 보면 버블 정렬과 반대되는 정렬 방법 같다는 생각이 든다.

세 정렬 방법의 차이점

• 버블 정렬
  • 버블 정렬 같은 경우엔 앞, 뒤 데이터를 비교하며 계속 swap 메서드를 실행한다.
  • 최악의 경우 모든 앞 뒤 데이터를 스왑 하는 경우가 발생한다. (n번의 스왑 * 사이즈-1)
  • 셋 중에 가장 느리지만 단순하다.
• 선택 정렬
  • 선택 정렬의 경우 단순히 모든 데이터를 순회 후 가장 작거나 큰 데이터의 인덱스를 기억해놓고 한 번의 스왑만 실행한다. 버블 정렬보다 훨씬 빠르다.
• 삽입 정렬
  • 삽입 정렬의 경우는 모든 데이터를 순회하지 않고 각 인덱스 별로 앞으로 순회하며 해당 인덱스의 데이터보다 작은 값이 존재할 때까지 검색 후 스왑을 실행한다.
  • 선택 정렬 같은 경우엔 사이즈 n만큼의 검색 후 스왑을 진행한다면 삽입 정렬은 1++ <n 이런 식으로 검색 시간도 적게 걸린다.

마무리

• 버블정렬은 잘 안 쓰인다고 합니다. (정렬할 때 많이 써왔던 거 같은데..)
• 삽입 정렬과 선택 정렬 중에서 잘 골라서 사용하면 된답니다.
  • 삽입 정렬이 선택 정렬보다 빠른 이유가 모든 아이템을 순회하지 않기 때문에라고 하는데..  그러면 선택 정렬은 한 번의 스왑만 진행하지만 삽입 정렬은 앞에 작은 값이 존재할 때까지 스왑을 진행하는데 이런 거에 대한 성능상 차이는 없을까..?라는 생각이 듭니다.
    • 그래서 누가 삽입 정렬은 배열의 크기가 클수록 효율이 떨어진댔는데 그게 그 말이었나? 싶습니다.
    • 그러면 차라리 선택정렬만 쓰는 게 낫겠다는 생각이 듭니다.
• 이름이 어려워서 겁먹었는데 생각보다 별거 없는 것 같습니다. 훗훗