자료구조 스터디 2주차

2-1) 버블정렬

로직이 단순하고 구현이 쉽다는 장점이 있다.

데이터의 인접요소끼리 먼저 비교하고 swap을 통해 정렬한다.

시간복잡도는 n^2으로 다른 정렬보다 많은 시간이 걸린다.

 

앞에서부터 뒤로가며 요소를 비교해 정렬하여 맨 마지막 인덱스에 위치하게되는 요소는 가장 큰 요소인게 확정된다. 따라서 루프를 1회 실행할때 마다 마지막에 위치하게되는 요소가 확정되어 n^2의 시간복잡도를 가지게 된다.  

 

만약 특정 루프의 전체 영역에서 한번도 스왑이 일어나지 않았다면 전체가 정렬되어있다는 의미이므로 루프를 탈출해도된다.

 

2-2) 선택정렬

최대나 최소의 데이터를 찾아가며 선택하는 방법. n^2의 시간복잡도로 빠른 방법은 아님.

정렬에 따라 최댓값또는 최솟값을 찾고 남은  정렬부분 가장 앞 데이터와 스왑하는 방식.

 

2-3) 삽입정렬

이미 정렬된 데이터 속에 정렬되지 않은 데이터를 적절한 위치에 삽입하는 방식. 구현은 쉽지만 시간복잡도는 n^2으로 다른 정렬보다 많은 시간이 걸린다.

정렬된 범위가 정렬하고자 하는 데이터의 크기와 같아진다면 정렬이 완료된 것임.

 

• 현재 인덱스의 데이터 값 선택.
• 데이터가 삽인될 위치를 선택한다.
• 삽입 위치부터 선택 인덱스의 위치까지 shift 연산을 수행한다.
• index++연산을 수행한다.
• 전체 데이터의 크기만큼 인덱스가 커질때 까지 반복한다.

적절한 위치에서 이진탐색등 알고리즘을 이용해 시간복잡도를 줄일 수 있다.

 

인덱스의 삽입 위치를 찾앗더라도 shift연산에서 많은 시간이 소요되기 때문에 시간복잡도를 줄이기 쉽지 않음.

 

 

2-4) 퀵정렬

피벗을 선택해 해당값보다 큰 데이터와 작은 데이터로 분류해 정렬하는 알고리즘.

피벗을 중심으로 두 집합을 나눠 정렬함.

n*log(n)의 시간복잡도를 갖는다. 구현이 생각보다 어렵다.

 

• pivot설정
• start와 피벗을 비교해 피벗보다 스타트 값이 작다면 스타트를 오른쪽으로 한칸 이동
• end와 피벗을 비교해 엔드 값이 작다면 엔드 값을 한칸 왼쪽으로 이동
• 스타트 데이터가 피벗보다 크고 엔드 데이터가 피벗보다 작다면 스타트와 엔드 데이터를 swap 하고 스타트는 오른쪽으로 엔드는 왼쪽으로 한칸 이동
• 스타트와 엔드가 만날때 까지 반복
• 스타트와 엔드가 만나면 만난지점에서 가르키는 데이터와 피벗의 데이터를 비교해 피벗이 크다면 오른쪽에 작다면 왼쪽이 피벗의 데이터를 삽입한다
• 데이터가 정렬될때 까지 반복

2-5) 병합정렬

분할정복 방식을 이용해 데이터를 분할하고 분할 집합을 정렬하며 합치는 알고리즘. 시간복잡도는 O(n*log(n))

 

데이터를 더이상 나눠지지 않을 수준의 부분 그룹으로 나눈다.

두 그룹을 합치면서 정렬해준다. 

각 덩어리들은 정렬이 완료된 상태이다.

 

투 포인터 개념을 사용하여 왼쪽 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 정답 배열에 추가하고 포인터를 오른쪽으로 한칸 이동시킨다. 

 

2-6) 기수정렬

 

시간복잡도가 가장짧은 정렬방법이다. 이론상 이해는 쉽지만 각 자릿수에 대해 큐를 생성하는 등 구현이 어려울 수 있음.

 

 

전체 값을 비교 하지 않는 않는 특이한 정렬. 값을 놓고 비교할 자릿수를 정한다음 해당 자릿수만 비교함.

10개의 큐를 이용한다(0~9). 각 큐는 각 값의 자릿수를 의미함. 

예를들어 80 은 1의자리 숫자가 0이라 0버 큐에 삽입하고 10의 자리 숫자는 8이니 8번 큐에 삽입한다.

 

백준 11399 삽입정렬 예제 풀이)

 

n=int(input())
lis_time=[]
time_sort=[]
time=input()
lis_time=list(map(int, time.split()))
total_time = [0] * n 

for i in range(n):
    min_index = i
    for j in range(i + 1, n):
        if lis_time[min_index] > lis_time[j]:
            min_index = j
    lis_time[i], lis_time[min_index] = lis_time[min_index], lis_time[i]

for k in range(n):
    total_time[n-k-1]=sum(lis_time[:k])+lis_time[k]

print(sum(total_time))

 

최소시간은 시간이 적게 걸리는 사람 순으로 순서를 정렬하였을 때 이므로 삽입 정렬을 이용하여 풀이하였다.

삽입 정렬을 완료한 이후 sum 함수를 이용하 각 소요시간을 구해 리스트에 삽이한 후 그 값을 sum하여 전체 최소 시간을 구하였다.