array.c File Reference

Contains definitions of routines supported by arrays. More...

#include "array.h"

Go to the source code of this file.

Functions
void	bubble_sort (t_gen a, int n, t_dparams *op)
	Bubble sort is simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order It has an O(n2) time complexity More...
void	selection_sort (t_gen a, int n, t_dparams *op)
	Selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity More...
void	insertion_sort (t_gen a, int n, t_dparams *op)
	Insertion sort builds the final sorted array one item at a time. It has an O(n2) time complexity More...
int	quick_sort_partition (t_gen a, int lo, int hi, t_dparams *op)
	Util function to be used by quick sort for sorting partitions More...
void	quick_sort (t_gen a, int n, t_dparams *op)
	Quicksort is an in-place sorting algorithm is a divide and conquer algorithm which relies on a partition operation: to partition an array, an element called a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and in-place. Worst case complexity of O(n2) and average of O(nlogn) More...

Detailed Description

Contains definitions of routines supported by arrays.

Definition in file array.c.

Function Documentation

bubble_sort()

void bubble_sort	(	t_gen	a,
		int	n,
		t_dparams *	op
	)

Bubble sort is simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order It has an O(n2) time complexity

Parameters

a	- Pointer to array
n	- size of array
op	- Data type specific params for operation such as compare and swap

Returns

- NA

Definition at line 17 of file array.c.

insertion_sort()

void insertion_sort	(	t_gen	a,
		int	n,
		t_dparams *	op
	)

Insertion sort builds the final sorted array one item at a time. It has an O(n2) time complexity

Parameters

a	- Pointer to array
n	- size of array
op	- Data type specific params for operation such as compare and swap

Returns

- NA

Definition at line 67 of file array.c.

quick_sort()

void quick_sort	(	t_gen	a,
		int	n,
		t_dparams *	op
	)

Quicksort is an in-place sorting algorithm is a divide and conquer algorithm which relies on a partition operation: to partition an array, an element called a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and in-place. Worst case complexity of O(n2) and average of O(nlogn)

Parameters

a	- Pointer to array
n	- size of array
op	- Data type specific params for operation such as compare and swap

Returns

- NA

Definition at line 122 of file array.c.

quick_sort_partition()

int quick_sort_partition	(	t_gen	a,
		int	lo,
		int	hi,
		t_dparams *	op
	)

Util function to be used by quick sort for sorting partitions

Parameters

a	- Pointer to array
l	- idx to partition start
h	- idx to partition end
op	- Data type specific params for operation such as compare and swap

Returns

- index of pivot

Definition at line 94 of file array.c.

selection_sort()

void selection_sort	(	t_gen	a,
		int	n,
		t_dparams *	op
	)

Selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity

Parameters

a	- Pointer to array
n	- size of array
op	- Data type specific params for operation such as compare and swap

Returns

- NA

Definition at line 40 of file array.c.