World of Algorithm

Abstract

Sorting is one of the most common applications in Computer Science through the data values are arranged per sorting. There are many sorting algorithms which are complex and simple sorting algorithms. In this study, insertion sort, quicksort 2 way, quicksort 3 way, and bucket sort were used. According to experiments, some results about the performance of sorting methods were obtained. Results were showed in graphs.

Introduction

Sorting  is a sequence of items is one of the pillar of computer science A sorting algorithm is an algorithm that organizes elements of a sequence in a certain order. There are many advantages sorting algorithms like memory efficiency and time efficiency. In this experiment, I evaluated time efficiency on different sorting algorithms. It ıs showed performance of different algorithms on different input size in several implementations by calling time functions.

Experiment

In this program, a random unsorted array is organized according to size getting from user are generated, there are four different sorting algorithm methods which are insertion sort, quicksort 2 way, quicksort 3 way, and bucket sort.

Bucket sort

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavor. Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm.

Bucket sort to be {\displaystyle O(n)}O(n) on average, the number of buckets n must be equal to the length of the array being sorted, and the input array must be uniformly distributed across the range of possible bucket values. If these requirements are not met, the performance of bucket sort will be dominated by the running time of next Sort, which is typically {\displaystyle O(n^{2})}O( )insertion sort.

Insertıon sort

 Insertion sort  iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (O(n)). The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (O(n²)).

Quick Sort

The quick sort [4] works on the divide-and-conquer principle. First, it partitions the list of items into two subsists based on a pivot element. All elements in the first sub list are arranged to be smaller than the pivot, while all elements in the second sub list are arranged to be larger than the pivot. The same partitioning and arranging process is performed repeatedly on the resulting sub lists until the whole list of items are sorted.

Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n²) comparisons, though this behavior is rare.

Algorithm	Time Complexity			Advantage/Disadvantage
	Best	Average	Worst
Quicksort(2-way)	O(n	O(n	O()	1. Fastest sorting algorithm in practice but sometime unbalanced partition can lead to very slow sort. 2. Available in many slandered libraries. 3. O (log n) space usage. 4. Unstable sort and complex for choosing a good pivot element.
Quicksort(3-way)	O(n	O(n	O()
Insertion Sort	O(n)	O()	O()	1. Efficient for small list and mostly sorted list. 2. Sort big array slowly. 3. Save memory
Bucket Sort	O(n)	O(n)	O()	1. Stable, fast. 2. Valid only in range o to some maximum value M. 3. Used in special cases when the key can be used to calculate the address of buckets.

Result

As shown in the Figure 1, array size increasing from left to right how long it takes for each sorting. I organized graph number of values on the horizontal axes, time is on the vertical axis, and time is second. According to graph, bucket sort is the most efficient in terms of time. After bucket sort, quick sort three way is best. Then quick sort two way and insertion sort is the worst.

Table 1

	Insertion Sort	Quick Sort 2 way	Quick Sort 3 way	Bucket
10	0	0	0	0
100	0	0	0	0
1000	0	0	0	0
10000	0,078	0,002	0	0
50000	1,989	0,016	0,008	0,001
100000	7,927	0,038	0,024	0,003

Conclusion

In this project, I used a random array and compared which algorithm sorting is more efficient in terms of complexity. According to my graph, bucket sorting is the best sorting. Insertion sort is the worst sorting.

Preparing by Emre Akkaya