동적 슬롯
의미: 슬롯의 개수를 가변적으로 관리하는 방법
최초 일정한 크기의 슬롯을 준비하되 만약 버킷이 가득찰 정도로 데이터가 들어온다면 슬롯 크기를 실행중에 늘릴 수 있는데 이는 동적 배열이나 연결 리스트를 사용해야 가능하다.
동적 배열을 사용한다면 해시테이블은 포인터 배열이 될 것이며, 연결 리스트를 사용한다면 각 버킷이 슬롯 연결 리스트의 진입점인 head를 저장해야할 것이다.
정렬이란
임의의 자료 집합을 일정한 기준에 따라 나열하는 것
정렬은 여러 방법이 있는데,
- 자료의 작은 것을 먼저 나열하는 것을 오름차순
- 자료의 큰것을 먼저 나열하는 것을 내림차순
- 정렬의 원리는 레코드의 키들을 비교해보고 순서를 바꿀 필요가 있는 레코드의 정렬이 완료될 때까지 반복
하는 것이 모두 정렬의 방법이다.
그 중에서도 가장 간단한 정렬 알고리즘이 버블 정렬이다.
버블 정렬
레코드의 선두부터 인접 요소를 비교하여 큰 값을 뒤로 보내는 방식으로 정렬하는 알고리즘
C++에서 버블정렬
#include<stdio.h>
#include <string.h>
void Swap(char* a, char* b) { // char* a => 포인터 변수(주소값을 담을 변수)
char temp = *a;
*a = *b; // *a => 포인터 변수가 가리키고 있는 실제 값
*b = temp;
}
void BubbleSort(char* str, int len) {
for (int i = 0; i < len - 1; i++) { // 전체 비교 횟수
for (int j = 1; j < len - i; j++) {
if (str[j - 1] > str[j]) {
Swap(&str[j - 1], &str[j]);
}
}
printf("정렬 중의 문자열: %s\n", str);
}
}
void main() {
// 1. 문자열 정렬
char str[] = "algorithm";
int len = strlen(str);
printf("정렬 전의 문자열: %s\n", str);
if (str[0] > str[1]) {
Swap(&str[0], &str[1]);
}
BubbleSort(str, len);
printf("정렬 후의 문자열: %s\n", str);
}C++에서 작성한 버블정렬을 JS로 그려보면 아래 코드와 동일하다.
자바스크립트에서 버블정렬
var arr = [54, 34, 25, 15, 55];
console.log("정렬 전: ", arr);
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 1; j < len - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
return arr;
}
const sortedarr = bubbleSort(arr);
console.log("정렬 후: ", sortedarr);다만 JS에서는 정렬을 위한 sort()와 같은 내장함수를 제공하고 있기에 참고하면 좋다.
선택 정렬
최소값을 찾아 앞쪽으로 이동하기를 배열 크기만큼 반복하는 정렬 방법
: 배열에서 가장 작은 값을 찾아 처음으로 일단 보낸 뒤, 첫번째 요소는 제외하고 남은 요소들 중에 제일 작은 값을 찾아 선두로 보내기를 배열끝까지 반복하면서 작은 순서대로 계속 앞쪽으로 이동하므로 반복이 끝나면 모든 요소를 순서대로 정렬하는 방법이다.
C++에서 선택정렬
#include<stdio.h>
#include <string.h>
void Swap(char* a, char* b) { // char* a => 포인터 변수(주소값을 담을 변수)
char temp = *a;
*a = *b; // *a => 포인터 변수가 가리키고 있는 실제 값
*b = temp;
}
void SelectectedSort(char* str, int len) {
int minidx = 0;
int j = 0;
for (int i = 0; i < len - 1; i++) {
for (j = i + 1, minidx = i; j < len; j++) {
if (str[minidx] > str[j]) {
minidx = j;
}
}
if (minidx != i) {
Swap(&str[minidx], &str[i]);
}
}
}
void main() {
char str[] = "algorithm";
int len = strlen(str);
printf("정렬 전의 문자열: %s\n", str);
SelectectedSort(str, len);
printf("정렬 후의 문자열: %s\n", str);
}JavaScript에서 선택정렬
const arr = [64, 34, 25, 12, 22, 11, 90];
function selectSort(arr) {
const len = arr.length;
let minidx = 0;
for(let i = 0; i < len-1; i++) {
let minidx = i;
for (let j = i+1; j < len; j++) {
if(arr[minidx] > arr[j]) {
minidx = j;
}
}
if (minidx !== i) {
let temp = arr[i];
arr[i] = arr[minidx];
arr[minidx] = temp;
}
}
return arr;
}
console.log(selectSort(arr));퀵 정렬
큰 배열을 일정한 기준값을 경계로 하여 기준값보다 큰 값들과 작은 값들로 구성된 작은 두 개의 배열로 분할한 뒤, 각 배열을 똑같은 방법으로 다시 정렬하는 방법으로 이름처럼 속도가 빠른 정렬 알고리즘
그림과 같이 n을 기준값으로 내부 요소값이 돌아가면서 n과 값을 비교하여 위치를 변경해 나가다가 n과 역전이 일어나면 해당 기준값과 비교값의 위치를 변경하면서 알고리즘 실행을 종료한다.
C++에서 퀵정렬
#include<stdio.h>
#include <string.h>
void Swap(char* a, char* b) { // char* a => 포인터 변수(주소값을 담을 변수)
char temp = *a;
*a = *b; // *a => 포인터 변수가 가리키고 있는 실제 값
*b = temp;
}
void quickSort(char* str, int len) {
int left = 0;
int right = 0;
char key = str[len-1];
if (len <= 1) return;
for (left = 0, right = len - 2;;left++, right--) {
while (str[left] < key) left++;
while (str[right] > key) right--;
if (left >= right) break;
Swap(&str[left], &str[right]);
}
Swap(&str[left], &str[len-1]); // 기준값과 left의 값 교환
quickSort(str, left); // 왼쪽 구간
quickSort(str+left+1, len-left-1); // 오른쪽 구간
}
void main() {
char str[] = "algorithm";
int len = strlen(str);
printf("정렬 전의 문자열: %s\n", str);
quickSort(str, len);
printf("정렬 후의 문자열: %s\n", str);
}