TIL - 2024/03/24

큐 (Queue)

먼저 넣은 데이터를 먼저 꺼내는 선입선출(First-In-First-Out) 구조

• enqueue - 데이터 추가
• dequeue - 데이터 꺼내기
• front - 데이터를 꺼내는 쪽
• rear - 데이터를 넣는 쪽

링 버퍼로 큐 구현하기

배열로 큐를 구현할 때는 배열안의 원소를 이동해주어야했지만 링 버퍼 구조로 구현하는 경우 배열안의 원소 이동없이 큐를 구현할 수 있다.

정렬

내부정렬, 외부정렬

• 내부 정렬 - 정렬할 데이터가 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘
• 외부 정렬 - 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우 사용하는 알고리즘
  
  

버블 정렬 (Bubble Sort) -> O(n^2)

이웃한 두 원소의 크기를 비교해서 필요에 따라 위치를 교환하는 알고리즘, 단순 교환 정렬

모든 원소의 크기를 비교하기 때문에 상당히 비효율적인 정렬알고리즘이다. 하지만 비교 과정에서 비교를 패스하는 구간을 잘 설정하면 약간의 알고리즘 개선이 가능하다.

단순 선택 정렬 -> O(n^2)

가장 작은 원소부터 선택해서 알맞은 위치로 옮기는 작업을 반복하는 정렬 방법

1. 정렬하지 않은 부분에서 값이 가장 작은 원소를 선택
2. 가장 작은 원소와 정렬하지 않은 부분의 맨앞 원소를 교환한다.

단순 선택 정렬의 경우 최소 값을 구하는 과정, 모든 배열을 순회하는 과정으로 인해서 복잡도가 n^2이다.

단순 선택정렬의 경우 같은 값을 정렬하는 경우 두 원소의 위치가 바뀔 수 있다는 점에서 안정적이지 않은 정렬 방법이다.

단순 삽입 정렬 -> O(n^2)

주목한 원소보다 더 앞쪽에 알맞은 위치로 삽입하여 정렬하는 알고리즘. 단순 선택정렬과 달리 가장 작은 원소를 선택하지 않는다는 차이점이 있다.

def insertion_sort(arr):
    n = len(arr)
    	
    for i in range(1, n):
    	j = i
    	temp = a[i]
    
    	while j > 0 and a[j - 1] > temp:
    		a[j] = a[j - 1]
    		j -= 1
    			
    	a[j] = temp	
    			

단순 삽입 정렬의 경우 배열이 길어질 수록 검색, 교환 비용이 커지기 때문에 이진 탐색을 활용해 검색 비용을 줄인 이진 삽입 정렬도 활용 가능하다.