PUCIT bookstore: sorting

Showing posts with label sorting. Show all posts

Friday, 21 April 2017

DSA Lab - Cheat Sheet Time complexity (Big-O) of different searching and sorting algorithms

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(log(n))`
Mergesort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Timsort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Selection Sort	`Ω(n^2)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tree Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(n)`
Shell Sort	`Ω(n log(n))`	`Θ(n(log(n))^2)`	`O(n(log(n))^2)`	`O(1)`
Bucket Sort	`Ω(n+k)`	`Θ(n+k)`	`O(n^2)`	`O(n)`
Radix Sort	`Ω(nk)`	`Θ(nk)`	`O(nk)`	`O(n+k)`
Counting Sort	`Ω(n+k)`	`Θ(n+k)`	`O(n+k)`	`O(k)`
Cubesort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`

DSA Lab Assignment 1 - Time and space complexity of different data structures & algorithms

Q 1:

Write the time and space complexity of the following data structures:

Array
Stack
Queue
LinkedList
HashTable
BinarySearchTree
AVL

Also write the time complexity of Insertions, Deletion and Access operations of above mentioned data structures.

Q 2:

Write the time and space complexity of the following algorithms:

Quick Sort
Selection Sort
Bubble Sort
Merge Sort
Insertion Sot
Linear Search
Binary Search

DSA Lab 4 - Recursion & Sorting Algorithems

Task 1:

Implement the following algorithms recursively:

sumOfArray() // This function will take an integer array as input and output its sum.
computeFactorial() //This function will take an integer as input and output its factorial
displayFibonacciSeries() //This function will take an integer as input and output that many terms of fibonacci series. e.g input = 6 then output = 1 1 2 3 5 8

Task 2:

Implement the following sorting algorithms recursively:

mergeSort()
quickSort()

Note: we have implemented these sorting algorithms before in lab 2. This time we have to implement them recursively.

Sunday, 2 April 2017

DSA Lab 2 - Implementation of Sorting and searching algorithms

Task # 1:
Implement the following sorting algorithms:

Selection sort
Insertion sort
Quick sort
Merge sort
bubble sort

Note: Your Implementation should contain a class named "mySort". You have to write a separate function of all above mentioned sorting algorithms in your class "mySort". Then you can call and test your algorithms in Main as "mySort.selectionSort()". In your main function you have to take input from a file "input.txt" and show the results on console.

Task # 2:

Implement the following sorting algorithms:

Binary Search

Your have to perform binary search on strings this time. (Hint: convert word into number by adding up the ASCII code of each letter in the word.)

Note: Your Implementation should contain a class named "mySearch". You have to write a separate function of binary search algorithm in your class "mySearch". Then you can call and test your algorithms in Main as "mySearch.binarySearch()". In your main function you have to take input from a file "input.txt" and show the results on console.