# sort
## using qsort in c
1. function:
int comparator(const void *x, const void *y);
2. if x should go before y : >0
3. if x is equivalent to y : 0
4. if x should go after y : <0

int compare(const void *x_void, const void *v_void){
    int x = *(int*)x_void;
    //We should first cast the pointer into specific type
    //And then we use *to dereference it
    int y = *(int*)y_void;
    return x - y;
    //If x - y > 0
    //x should go before y
    //-> x > y
}

5. qusort(array, length, sizeof(int), compare);
## insertion sort

*def insertionsort(list):  
    for i in range(1, len(list)):  
        current = list[i]  
        j = i - 1  
        while j >= 0 and current < list[j]:  
            list[j+1] = list[j]  
            j -= 1  
        list[j+1] = current  
    return list
def main():
    list = [99, 0, 5, 20, 123, 0, -1, 72, 21, 22, 13, 8, 7, 67, 29, 1, 2, 4]
    insertionsort(list)
    print(list)
    list = [3, 9, 2, 1]
    insertionsort(list)
    print(list)*

## merge sort

*def mergesort(list):
    length = len(list)
    if length == 1:
        return list
    mid = length // 2
    left = mergesort(list[:mid])
    right = mergesort(list[mid:])
    return merge(left, right)


def merge(left, right):
    output = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            output.append(left[i])
            i += 1
        else:
            output.append(right[j])
            j += 1
    output.extend(left[i:])
    output.extend(right[j:])
    return output


def main():
    unsorted = [99, 0, 5, 20, 123, 0, -1, 72, 21, 22, 13, 8, 7, 67, 29, 1, 2, 4]
    sorted = mergesort(unsorted)
    print(sorted)
    unsorted = [3, 9, 2, 1]
    sorted = mergesort(unsorted)
    print(sorted)*

## quick sort

#include <stdio.h>
#include <stdlib.h>
int len = 0;
void quick(int left, int right, int arr[]){
	if(left < 0 || right > len || right - left < 1) return ;
	int i = left, j = right;
	int p = arr[right];
	while(i < j){
		while(i < j && arr[i] <= p){ ++i;}
		while(i < j && arr[j] >= p){ --j;}
		if(i < j){
			arr[i] ^= arr[j] ^= arr[i] ^= arr[j];
		}
	}
	arr[right] = arr[i];
	arr[i] = p;
	quick(left, i - 1, arr);
	quick(i + 1, right, arr);
}
void quick_HIGH(int left, int right, int arr[]){
	if(left < 0 || right > len || right - left < 1) return ;
	int i = left, j = right;
	int p = arr[left];
	//We have to pass the pivot first, so if we choose right side as a pivot,
	//then we have to let i go first
	while(i < j){
		while(i < j && arr[j] <= p){ --j;}
		while(i < j && arr[i] >= p){ ++i;}
		if(i < j){
			arr[i] ^= arr[j] ^= arr[i] ^= arr[j];
		}
	}
	arr[left] = arr[i];
	arr[i] = p;
	for(int i = 0; i < len; ++i){
		printf("%d ", arr[i]);
	}
		printf("\n");
	quick_HIGH(left, i - 1, arr);
	quick_HIGH(i + 1, right, arr);
}
int main()
{
	int arr[] = {1, 4, 7, 3, 5, 6 ,8};
	len = sizeof(arr)/4;
	
	quick(0, sizeof(arr) / 4 - 1, arr);
	printf("before:\n");
	for(int i = 0; i < sizeof(arr)/4; ++i){
		printf("%d ", arr[i]);
	}
	printf("\nafter:\n");
	quick_HIGH(0, sizeof(arr) / 4 - 1, arr);
	for(int i = 0; i < sizeof(arr)/4; ++i){
		printf("%d ", arr[i]);
	}
    return 0;
}