Scribd
Upload
28 views

Cheatsheet

The document describes the algorithms for selection sort, insertion sort, quicksort, merge sort, and heap sort. Each algorithm is explained through pseudocode that shows the key steps and recursive logic for sorting an array of integers from lowest to highest value.

Uploaded by

Hữu Hoàng
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
28 views

Cheatsheet

The document describes the algorithms for selection sort, insertion sort, quicksort, merge sort, and heap sort. Each algorithm is explained through pseudocode that shows the key steps and recursive logic for sorting an array of integers from lowest to highest value.

Uploaded by

Hữu Hoàng
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

void selectionSort(int array[], int size)

{
for (int step = 0; step < size - 1; step++)
{
int min_idx = step;
for (int i = step + 1; i < size; i++)
{

// To sort in descending order, change > to < in this


line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}

// put min at the correct position


swap(&array[min_idx], &array[step]);
}
}

////////////////////////////////

void insertionSort(int array[], int size) {


for (int step = 1; step < size; step++) {
int key = array[step];
int j = step - 1;

// Compare key with each element on the left of it until an


element smaller than
// it is found.
// For descending order, change key<array[j] to key>array[j].
while (key < array[j] && j >= 0) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}

///////////////////////////////////////

Quick

// function to rearrange array (find the partition point)


int partition(int array[], int low, int high) {

// select the rightmost element as pivot


int pivot = array[high];

// pointer for greater element


int i = (low - 1);

// traverse each element of the array


// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {

// if element smaller than pivot is found


// swap it with the greater element pointed by i
i++;

// swap element at i with element at j


swap(&array[i], &array[j]);
}
}

// swap pivot with the greater element at i


swap(&array[i + 1], &array[high]);

// return the partition point


return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {

// find the pivot element such that


// elements smaller than pivot are on left of pivot
// elements greater than pivot are on righ of pivot
int pi = partition(array, low, high);

// recursive call on the left of pivot


quickSort(array, low, pi - 1);

// recursive call on the right of pivot


quickSort(array, pi + 1, high);
}
}

//////////////////////////

Merge
void merge(int arr[], int p, int q, int r) {

// Create L ← A[p..q] and M ← A[q+1..r]


int n1 = q - p + 1;
int n2 = r - q;

int L[n1], M[n2];

for (int i = 0; i < n1; i++)


L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

// Maintain current index of sub-arrays and main array


int i, j, k;
i = 0;
j = 0;
k = p;

// Until we reach either end of either L or M, pick larger


among
// elements L and M and place them in the correct position at
A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}

// When we run out of elements in either L or M,


// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

while (j < n2) {


arr[k] = M[j];
j++;
k++;
}
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two
subarrays
int m = l + (r - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted subarrays


merge(arr, l, m, r);
}
}

//////////////////////////

Heap

void heapify(int arr[], int N, int i)


{

// Initialize largest as root


int largest = i;

// left = 2*i + 1
int l = 2 * i + 1;

// right = 2*i + 2
int r = 2 * i + 2;

// If left child is larger than root


if (l < N && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest


// so far
if (r < N && arr[r] > arr[largest])
largest = r;

// If largest is not root


if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected


// sub-tree
heapify(arr, N, largest);
}
}

// Main function to do heap sort


void heapSort(int arr[], int N)
{

// Build heap (rearrange array)


for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);

// One by one extract an element


// from heap
for (int i = N - 1; i > 0; i--) {

// Move current root to end


swap(arr[0], arr[i]);

// call max heapify on the reduced heap


heapify(arr, i, 0);
}
}
////////////////////////////////////////

You might also like