정렬 알고리즘 / 이코테_정렬

다음과 같이 n개의 양의 정수 중에서 가장 작은 수를 찾는 알고리즘에서 기억 장소의 크기와 수행횟수를 구하기.

Find_MIN (int array[], int MIN)
{
	int i;
    MIN = array[0];
    for (i = 1; i < n; i++)
    	if (MIN > array[i]) MIN = array[i];
    return (MIN);
}

피보나치 수열 알고리즘의 빈도수 구하기

fibonacc(n)
	if (n<0) then
    	stop;
    if (n<=1) then
    	return n;
    f1 <- 0;
    f2 <- 1;
    for (i<-2; i <= n; i <- i+1) do {
    	fn <- f1+f2;
        f1 <- f2;
        f2 <- fn;
    }
    return fn;
end

수식의 괄호 검사 알고리즘

testPair()
	exp <- Expression;
    Stack <- null;
    while (true) do {
    	symbol <- getSymbol(exp);
        case{
        	symbol = "(" or "[" or "{":
            	push(Stack, symbol);
            symbol = ")":
            	open_pair <- pop(Stack);
                if (open_pair != "(" ) then return false;
            symbol = "]":
            	open_pair <- pop(Stack);
                if (open_pair != "[" ) then return false;
           	symbol = null:
            	if (isEmpty(Stack)) then return true;
                else return false;
            else:
        }
    }
end testPair()

< 시간복잡도 비교 >

이진탐색
O(logn)

합병정렬	퀵정렬	힙정렬
O(nlogn)	O(nlogn)	O(nlogn)

버블정렬	삽입정렬	선택정렬	쉘정렬
O(n2)	O(n2)	O(n2)	O(n1.5)

퀵 정렬 코드

def quicksort(array):
	if len(array) < 2:
    	return array
    else:
    	pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
        
 print quicksort([10, 5, 2, 3])

버블 정렬

int i, j, temp;
for(i = 0; i < n-1; i++)
	for (j = 0; j < n-i-1; j++)
    	if(array[j] > array[j+1]) {
        temp = array[j];
        array[j] = array[j+1];
        array[j+1] = temp;
        }
}

삽입정렬 코드 1

for i = 1 to n-1 {
	CurrentElement = A[i]
    j <- i-1
    while (j>=0) and (A[j]>CurrentElement) {
    	a[j+1] = a[j]
        j <- j - 1
    }
    A[j+1] <- CurrentElement
}
return A

삽입정렬 코드 2

def ins_sort(a):
	n = len(a)
    for i in range(1, n):
    	key = a[i]
        j = i-1
        while j>=0 and a[j] > key:
        	a[j+1] = a[j]
            j -= 1
        a[j+1] = key

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)

삽입정렬 코드 3

def find_ins_idx(r, v):
	for i in range(0, len(r)):
    	if v < r[i]:
        	return i
    return len(r)
    
def ins_sort(a):
	result = []
    while a:
    	value = a.pop(0)
        ins_idx = find_ins_idx(result, value)
        result.insert(ins_idx, value)
return result

d = [2, 4, 5, 1, 3]
print(ins_sort(d))

쉘정렬 코드 1

for each gap h = [h0>h1>...>hk = 1]
	for i = h to n-1 {
    	CurrentElement = A[i]:
        j = i
        while(j>=h) and A[j-h] > CurrentElement) {
        	A[j] = A[j-h]:
            j = j-h
        }
        A[j] = CurrentElement:
}
return 배열 A

쉘정렬 코드 2

def shell_sort(a):
	h = 4
    while h >= 1:
    	for i in range(h, len(a)):
        	j = i
            while (j>=h) and a[j] < a[j-h]:
            	a[j], a[j-h] = a[j-h], a[j]
                j -= h
            h //= 3

a = [55, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
print('정렬 전:\t', end = '')
print(a)
shell_sort(a)
print('정렬 후:\t', end = '')
print(a)

이코테 정렬 알고리즘 풀이

국영수

a = [(5, 1, 5), (3, 5, 5), (3, 1, 9), (3, 1, 1)]
a.sort()

print(a)

n = int(input())
students = []

for _ in range(n):
    students.append(input().split())

students.sort(key = lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

안테나

n = int(input())
data = list(map(int, input().split()))
data.sort()

print(data[(n-1) // 2])

실패율

def solution(N, stages):
    answer = []
    length = len(stages)

    for i in range(1, N+1):
        count = stages.count(i) # 개수세기

        if length == 0:
            fail = 0
        else:
            fail = count / length

        answer.append((i, fail))
        length -= count

    answer = sorted(answer, key=lambda t:t[1], reverse = True)

    answer = [i[0] for i in answer]
    return answer

카드 정렬하기

import heapq

n = int(input())

heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap, data)

result = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)