정렬
정렬이란 데이터를 순서대로 나열하는 방법을 의미한다.
정렬을 통해 데이터를 나열하고 조금 더 효율적으로 탐색 할 수 있게 해준다.
아래 링크에 접속하면 정렬과정을 보여준다.
https://gfycat.com/dazzlinggracefulangelfish
버블정렬(bubble sort)
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
2단계 : [4, 6, 2, 9, 1]
6과 2를 비교합니다!
6 > 2 이므로 둘을 변경합니다!
[4, 2, 6, 9, 1] 이렇게요!
3단계 : [4, 2, 6, 9, 1]
6과 9를 비교합니다!
6 < 9 이면 그대로 둡니다.
4단계 : [4, 2, 6, 9, 1]
9와 1를 비교합니다!
9 > 1 이므로 둘을 변경합니다!
[4, 2, 6, 1, 9] 이렇게요!
5단계 : [4, 2, 6, 1, 9]
4와 2을 비교합니다!
4 > 2 이므로 둘을 변경합니다.
[2, 4, 6, 1, 9] 이렇게요!
6단계 : [2, 4, 6, 1, 9]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
7단계 : [2, 4, 6, 1, 9]
6와 1을 비교합니다!
6 > 1 이므로 둘을 변경합니다!
[2, 4, 1, 6, 9] 이렇게요!
8단계 : [2, 4, 1, 6, 9]
2와 4을 비교합니다!
2 < 4 이면 그대로 둡니다.
9단계 : [2, 4, 1, 6, 9]
4와 1을 비교합니다!
4 > 1 이므로 둘을 변경합니다!
[2, 1, 4, 6, 9] 이렇게요!
10단계 : [2, 1, 4, 6, 9]
2와 1을 비교합니다!
2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!선택정렬
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4] 이렇게요!
자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
[1, 2, 6, 9, 4] 이렇게요!
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
[1, 2, 4, 9, 6] 이렇게요!
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!삽입정렬
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 6을 받습니다.
4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
[4, 6, 2, 9, 1] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 2를 받습니다.
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
[2, 4, 6, 9, 1] 이렇게요!
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 9를 받습니다.
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
[2, 4, 6, 9, 1] 이렇게요!
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 1을 받습니다.
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요![자료구조] 스택 / 큐
스택(stack)
스택은 차곡차곡 쌓아 올린 형태의 자료구조이다.
가장 마지막에 삽입된 자료가 가장 먼저 삭제되며 이를 후입선출(LIFO , Last In First Out)구조 라고 한다.
스택이 넘치는 경우 stack overflow라고 하는데 그 유명한 사이트 stackoverflow의 이름이 여기서 유래 된것이란다.
스택의 활용
웹 브라우저 뒤로가기 : 가장 나중에 열린 페이지부터 다시 보여준다.
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력된다.
실행 취소 : 가장 나중에 실행 된 것부터 실행을 취소한다.
스택에서 제공하는 기능
push() : 맨 끝요소에 데이터 넣기
pop() : 맨 끝 요소 데이터 삭제
peek() : 맨 끝 요소 데이터 보기
isEmpty() : 스택이 비었는지 여부 반환
큐(queue)
큐는 줄을 서서 기다리는 것이라고 생각하면 쉽다, 먼저 들어온 것이 먼저 나가는 선입선출(FIFO , First In First Out) 이다.
큐는 한쪽 끝에서는 삽입작업, 다른 끝 쪽에서 삭제작업이 양쪽으로 이루어 진다.
삭제연산만 수행 되는 곳을 front(프론트) , 삽입연산만 수행 되는 곳을 rear(리어)로 정하여 연산작업이 수행된다.
큐의 활용
프로세스 관리 , 캐시(cache)구현 , 너비우선탐색(BFS)구현 등이 있다.
큐에서 제공하는 기능
enqueue(data) : 맨 뒤에 데이터 추가하기
dequeue() : 맨 앞의 데이터 삭제
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
