오름차순 정렬(ascending sort)

오름차순 정렬

• 낮은 수 부터 높은 수로 정렬하는 방식

파이썬으로 작성해 보았다.
예제1) 버블정렬(bubble sort)

x = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
for _ in range(len(x)):
    for i in range(len(x)-1):
        if x[i] > x[i+1]:
            x[i], x[i+1] = x[i+1], x[i]
print(x)

예제2) 선택 정렬(selection sort)

x = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
y = []
for i in range(len(x)):
    y.append(min(x))
    x.remove(min(x))
print(y)

더 좋아 보이는 방법들도 머릿속에는 있는데 아직 코딩실력이 못따라간다.

빅오표기법(Big-O notation)

• 알고리즘의 효율성을 평가하는 분석법

• 효율성의 순서
  : O(2^n) < O(n^2) < O(n log n) < O(n) < O(lng n) < O(1)

• 선택정렬 및 버블정렬의 수학식:등차수열 (10개의 수를 정렬할 때)

  • ex) 10 * (10 + 1) / 2
    -> N * (N + 1) /2
    -> N^2

• 따라서 선택정렬은 이 중 (O(n^2)) 단계이므로 그 효율성이 좋지 않다.

• 선택정렬과 버블정렬의 빅오 단계는 같지만 element의 교체횟수가 훨씬 많은 버블정렬의 속도가 훨씬 느리다(정렬 알고리즘 중에 버블정렬이 가장느리다).