Sorting (정렬)

1. 버블정렬
2. 선택정렬

알고리즘에 자주 쓰이는 정렬기법에는 다양한 기법이 있습니다.

• 버블정렬
• 선택정렬
• 삽입정렬
• 퀵 정렬
• 병합 정렬

버블정렬

• 인접한 레코드가 순서대로 되어 있지 않으면 Swap
• 전체가 정렬될 때까지 비교/교환을 계속한다.
• 알고리즘

1. n개의 리스트가 있는 경우 최대 n-1번의 루프를 돈다. (앞과 뒤의 레코드 한 개씩 비교하기 때문에)
2. 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다. 따라서 한번 Loop를 돌 때마다 비교횟수가 한 개씩 줄어든다.
3. 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.

   한 턴에서 Swap이 하나도 없었다면 모두 정렬된 상태이다.

for i in range(N):
  isSwap = false
    for j in range(i+1, N):
        if lst[i] > lst[j]:
            temp = lst[i]
            lst[i] = lst[j]
            lst[j] = temp
            isSwap = true
    if(!isSwap):
      break;

선택정렬

제자리 정렬이라고도 불린다.

• 주어진 데이터 중, 최소값을 찾고(선택해서) 데이터 맨 앞에 위치한 값과 교체하는 방법
• 알고리즘

1. 첫번째 인덱스 값부터 Stand(기준)으로 잡고, 그 인덱스의 오른쪽 요소를 모두 탐색해서 최소값을 찾는다.
2. 최소값을 Stand와 Swap하고, Stand는 전체 길이 – 1 (마지막 Stand는 비교할 필요X)만큼 반복한다.
3. Turn 을 진행할 때마다 맨 앞자리 숫자는 최소값이므로 비교할 필요가 없다.
4. 현재 Stand 가 최소값의 Index일 경우에는 Swap 하지 않는다.

for i in range(N):
    min_index = i
    for j in range(i+1, N):
        if lst[min_index] > lst[j]:
            min_index = j
    # 스와프
    if i != min_index:
        temp = lst[i]
        lst[i] = lst[min_index]
        lst[min_index] = temp