자료구죠 키워드 정리.

나열 방법 -> 탐색 및 검색을 잘 하게 하는 알고리즘 구조

선형: 연결 리스트, stack, queue, dequeu
비선형: Tree

stack
push: pop == 입력 방향, 출력방향이 하나임. 입출구가 하나인 박스공간.

Queue: 줄서기
Push:Pop == 단방향

Dequeu: 상호작용
Push:Pop == 양방향
a) 선택 정렬
->선택 정렬은 비교는 많지만, 교환은 적은 알고리즘이다.
 장점: 정렬된 상태를 역순으로 정렬시 효율적이다.
 단점: 정렬된 데이터에 소수의 데이터 추가시 이를 다시 정렬하기 위해서는 최악이다.

$ cat ages.txt
Bob 12
Jane 48
Mark 3
Tashi 54

$ sort -k2 -n ages.txt
Mark 3
Bob 12
Jane 48
Tashi 54

sort -n -k 7 /path/to/input
find . -type f -iname "pattern*" -ls |sort -n -k 7
find . -type f -iname "pattern*" -ls |sort -r -n -k 7

-r -정렬 결과를 반대.
-n -숫자 정렬
-k 7 -POS1에서 키 시작 즉, 7 번에서 정렬 키 시작
-s 정렬 안정화

b) 버블 정렬
시간복잡도: O(N^2)

->데이터를 하나씩 비교할 수 있어서 정밀하게 비교 가능하나 비교횟수가 많아지므로
성능면에서 좋은 방법이 아니다. 첫번째 원소부터 마지막 원소까지 비교가 끝나면 가장 큰 원소를 마지막 자리로 정렬한다.

# Bash 배열 정렬
# Bubble 정렬 사용
 
# 정적 배열 입력
arr = (10 8 20 100 12)
 
echo "Array in original order"
echo ${arr[*]}
 
# 버블 정렬 수행 
for ((i = 0; i<5; i++))
do
     
    for((j = i; j<5-i-1; j++))
    do
     
        if ((${arr[j]} > ${arr[$((j+1))]}))
        then
            # swap
            temp = ${arr[$j]}
            arr[$j] = ${arr[$((j+1))]} 
            arr[$((j+1))] = $temp
        fi
    done
done
 
echo "Array in sorted order :"
echo ${arr[*]}

출력 :
Array in sorted order :
8 10 12 20 100

c) 퀵정렬 >
시간복잡도
최악- O(N^2)
평균- O(NlogN)

->캐시라는 지역적 특성에 의해 실제적으로 NlogN보다 좋은 성능을 보여 가장 많이 사용하는 정렬이다. 단점으로는 안정성이없다. 안정성이 없다는 것은 정렬되기 이전의 데이터 동일한 데이터끼리의 순서를 정렬 후에도 유지하고 있는가이다.

d) 삽입정렬 >
시간복잡도 : O(N^2)

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해 고안된 삽입정렬이다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 비교적 비교횟수를 줄이고 , 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어난다.


e) 쉘 정렬 >
시간복잡도: O(N^1.25)

삽입정렬의 개념을 확대하여 일반화한 정렬방법이다. 알고리즘이 간단하여 간단히 구현할 수 있다. 수행능력도 삽입정렬보다 우수하다. 멀리있는 레코드들 끼리 비교 및 교환 될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬의 단점을 해결 할 수 있다.

f) 병합 정렬>
시간복잡도: O(NlogN)

작은 단위부터 정렬해서 정렬된 단위들을  계속 병합해가면서 정렬하는 방식이다. 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법이다. 안정성이 있으며 상당히 좋은 성능을 나타낸다. 큰 결점은 데이터 크기만한 메모리가 더 필요하다는 것이다.

g) 버킷정렬>
버킷정렬은 정렬대상의 키들을 일정한 범위로 구분해 버킷(통)에 넣고 그 버킷을 각각 정렬하는 방법이다.

특징: 키가 어떤 범위내에서 키값이 확률적으로 균등하게 분포되어 있을 때 적용하면 효과가 좋다.
  실행시간: 버켓에 넣는 시간 O(n)+정렬시간

사용하기 좋은 예: "Person 객체를 담은 아주 큰 배열이 있다고 하자. 이 배열에 담긴 객체들을 나이순으로 정렬하라"
  여기서 두 힌트를 얻을 수 있다.
1. 큰 배열이므로 효율성이 중요하다.
2. 나이에 따라 정렬하는 것이므로, 그 값의 범위가 좁게 제한되어 있음을 이용할 수 있다.

정렬 알고리즘들을 살펴보면, 아마 버킷정렬 또는 기수 정렬이 가장 적합하리라는 것을 눈치 챌 수 있을 것이다. 버킷을 작게 만들 수 있고(각 버킷에 1년)O(n)으 실행시간을 달성할 수 있다. 그렇다면 값의 범위가 작을 때 사용하기 좋은 정렬?