니트코드 10번 알고리즘 : Insertion Sort (Stable and Unstable Sort)

니트코등 링크 : https://neetcode.io/courses/dsa-for-beginners/10

Sorting중 첫 번째 방식인 Insertion Sort이다.

위의 사진과 같이 i 포인터를 옮겨가며 해당 원소부터 왼쪽에 있는 subarray를 정렬해가는 것이다. j 포인터를 사용해 i포인터가 가르키는 원소의 바로 왼쪽부터 비교해가며 위치를 swap하는 알고리즘이다. 

class Solution(object):

  def sortArray(self, nums):

    for i in range(1,len(nums)):

      j = i

      while (j >0 and nums[j-1] > nums[j] ):

        temp = nums[j-1]

        nums[j-1] = nums[j]

        nums[j] = temp

        j= j - 1      

    return nums

파이썬 코드이다. while문 조건 안에 j>0이 있는 점을 참고하자.

 

Stable Sort vs. Unstable Sort

위의 사진과 같이 동일한 값을 가진 7이더라도 해당 원소들이 sorting후에도 relative position이 항상 유지가 되면 stable sort, 그렇지 않으면 Unstable Sort이다.

Insertion Sort는 while문 조건에서 nums[j-1] > nums[j] 일때만 swap을 해주기 때문에 stable sort라는 것을 알 수 있다.