Power point presentation of Sorting Techniques

Power point presentation

1. OVERVIEW Abstract. Introduction. Types of Sorting. Time Complexity Chart. Visualization. Advantages. Disadvantages. Conclusion. References.

2. Abstract In this mini project we are going to design various sorting techniques graphically like Bubble sort, Insertion sort, Selection sort and Heap sort. The main aim of sorting algorithms is to rearrange a given array or list of elements according to the type of the sort. An Important key for algorithm design is to use sorting as a basic building block, because once a set of items are sorted many other problems becomes easy. Each sorting algorithm has its own time and space complexity. In this project we would be generating a web page in which various sorting techniques are graphically designed to analyse the working principle of each sorting method and each sorting algorithm is explained with detailed information.

3. Introduction In computer science, arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient algorithms to perform it have been developed. The most common uses of sorted sequences are: Making lookup or search efficient. Making merging of sequences efficient. Enable processing of data in a defined order. The opposite of sorting, rearranging a sequence of items in a random or meaningless order, is called shuffling. Sorting n-tuples can be done based on one or more of its components. More generally objects can be sorted based on a property. Such a component or property is called a sort key. For example, the items are books, the sort key is the title, subject or author, and the order is alphabetical.

4. TYPES OF SORTING There are different types of sorting techniques . Bubble Sort. Selection Sort. Insertion Sort . Merge Sort. Quick Sort. Heap Sort.

5. BUBBLE SORT Bubble sort examines the array from start to finish, comparing elements as it goes. Any time it finds a larger element before a smaller element, it swaps the two. In this way, the larger elements are passed towards the end. The largest element of the array therefore "bubbles" to the end of the array. Then it repeats the process for the unsorted portion of the array until the whole array is sorted

6. SELECTION SORT Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

7. INSERTION SORT This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort. The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of O(n^2), where n is the number of items.

8. MERGE SORT Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sub-list consists of a single element and merging those sub-lists in a manner that results into a sorted list. The List of size N is divided into a max of logN parts and the merging of all the sub-lists into a single list takes O(N) time, the worst case runtime of this algorithm is O( NlogN ).

9. QUICK SORT Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quick sort partitions an array and then calls itself recursively twice to sort the two resulting sub-arrays. This algorithm is quite efficient for large-sized data sets as its average and worst case complexity are of O(n^2), where n is the number of items.

10. HEAP SORT Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. Min-Heap:- Where the value of the root node is less than or equal to either of its children. Max-Heap:- Where the value of the root node is greater than or equal to either of its children. Note:- At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree. Note:- In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.

11. TIME COMPLEXITY CHART Time complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to process as a function of the amount of input. In other words, time complexity is, how long a program function takes to process a given input.

12. VISUALIZATION OF SORTING BUTTONS Each one of the Sorting button performs its own unique sorting technique operation. After completion of Sorting operation click on “Randomize Array” , to reset array in some random array. Helps in converting the sorted array into asc and desc order Helps in converting the array into randomized array

13. VISUALIZATION OF UNSORTED ARRAY Initially the canvas has a unsorted array based upon the values taken randomly. Each bar graph in the canvas represents the particular value of an array. Randomized array

14. VISUALIZATION OF SORTED ARRAY After completion of sorting technique the final output of sorted array is displayed on the canvas. The output of the sorted arrays can be displayed in two ways:- Ascending order. Descending order. The outputs of the following sorted arrays are shown in next slide.

15. SORTED ARRAYS DESCENDING ORDER ASCENDING ORDER

16. DELAY TIME:- It is used to control the speed of the sorting operations according to the value given on scrollbar. As we increase the delay time value the speed of operation decreases and as we decrease the delay time value the operation speed of the operation increases. The delay time values ranges from 100 milliseconds to 300 milliseconds.

17. ARRAY LENGTH:- Array length bar describes the size of the array in the canvas. As the size of the Array length bar increases the number of bars in the canvas increases. The array of length starts from size 10 to maximum size of 35 elements.

18. ADVANTAGES Bubble Sort:- It is most popular, easy to implement, requires less space and does not require additional storage. Insertion Sort:- It is simple and space requirement is minimal. Selection Sort:- It performs well on small list, it doesn’t require any additional storage. Merge Sort:- It can be applied to files of any size, It performs sorting techniques faster. Quick Sort:- It is regarded as best sorting algorithm, it is able to deal with huge list of items. Heap Sort:- Heap sort is widely used because of its efficiency and its memory usage is minimal.

19. Disadvantages Bubble Sort:- The main disadvantage of bubble sort is, it cannot deal with huge number of items. Insertion Sort:- The performance of insertion sort is not good as compared to other sorting techniques. Selection Sort:- It’s efficiency is poor when dealing with huge list of elements. Merge Sort:- It requires more space than compared to any other sorting technique. Quick Sort:- The worst case of quick sort is similar to the average performances of Bubble sort or Selection sort. Heap Sort:- It makes a tree of sorting elements because of which it requires more space.

20. CONCLUSION To sum up, in this mini project , different sorting techniques like Bubble Sort , Selection Sort, Insertion Sort , Merge Sort , Quick Sort and Heap Sort are explained and visualized how these processes are organized based on the type of algorithms, the user selects.

21. REFERENCES HTML-5 Black Book. www.w3schools.com www.tutorialspoint.com www.javascript.com

22. THANK YOU