삽입정렬 -스터디-

삽입정렬이란?

정렬되지 않은 부분의 데이터를 뽑아서 정렬된 부분의 적절한 위치에 삽입하는 방법이다.

말 그대로 삽입 해서 넣는 정렬 방법이다.

다른 정렬방식과는 다르게 앞의 원소들과 큰지 작은지 비교하여 정렬하는 방식이다.

앞의 원소와 비교해야하기 때문에 index1부터 시작한다. (제일 앞의 index는 0이다.)

리스트의 길이가 길 수 록 효율이 떨어진다.

공부 방법

정렬 순서를 차근차근 손으로 써가며 알아봤다. 손으로 쓰기 좀 길지만 길이가 5인 리스트를 정렬해 보았다.

삽입정렬은 두번째 원소인 index가 1인 원소부터 시작해야한다는 점을 기억하고 시작하자.

전체적인 흐름을 말하자면 삽입할 index와 비교할 index의 크기를 비교하여서 비교할 index가 더 크면 서로의 위치를 바꾸는 방식이다.

생각보다 간단한 정렬 방식인거 같다.

계속 위의 흐름대로 비교를 하다가 조건중 삽입할 index가 비교할 index보다 더 클때가 있는데 이럴땐 바로 break 걸어주면 된다.

이유는 삽입할 값이 더 크다면 왼쪽의 값들은 삽입할 index보다 작기때문에 더 비교할 필요가 없기때문이다. (오름차순 기준)

• data에 정렬이 안된 리스트가 담겨있다
• 기존 data 리스트 index1부터 시작하고 마지막 index까지 순회한다.
• 삽입할 index를 왼쪽 index들과 비교 (거꾸로 순회)
  • 값을 비교해서 왼쪽값이 더 크면 서로 위치 바꾸기

위 과정을 토대로 코딩한다면 아래와 같은 코드로 나타낼 수 있다.

def solution(data):
      for i in range(1, len(data)):
          for j in range(i, 0, -1):
              if data[j] < data[j - 1]:
                  data[j], data[j - 1] = data[j - 1], data[j]
            else:
                  break

    return data

if __name__ == '__main__':
      data = [5, 4, 3, 2, 1]
    print(solution(data))