Finding First and Last occurrence in sorted list

Finding first and last occurrence of given number in sorted list is a very easy problem and can easily solved by leaner search with worse case Time complexity O(n) .
But We can Achieve faster search of first and last occurrence of a number by exploiting sorted feature of list.
We can  search  occurrence of any number in sorted list in O(log(n)) Time Complexity by using Binary search Algorithm.

Quick Select -Finding K'th Largest

Quick select is one of very popular algorithm used to find k'th largest element in a list. It can be use to find median or finding k'th smallest element etc.

Finding K'th largest element looks easy , we just need to sort & get K'th largest . But here we are dealing with time so we need fastest way to do this

 Time complexity of Quick Select (average case) =O(n)

 Quick Select is basically modified version of Quick sort. In Quick Sort we need to sort all element but Quick select just want to know pivot value that divide array in given ratio.

Quick sort 

let a example we have 10 different number in array  & we want to find 3rd largest element.(we  assume 0..9 index array) then in sorted array its position should be (10-3)th Index.

Number Of Occurence

One Of very commonly asked problem in Job Interviews is To find number of occurrence of given word in given paragraph . This very easy question but people still make mistakes .

How to do it  :-

• Find first occurrence of first character of word in paragraph 
• If found >>  from that point check next character of word match with next character of paragraph
• Check until last character of word match with consecutive next character of paragraph
• If all character match increment  count by 1.
• Repeat all above statement but now search perform on paragraph started at index of end of last character until which our search is completed 

Insertion Sort , In Python

Insertion Sort is one of easiest & efficient way to sort small group of numbers . Using Python this algorithm is very very simple to implement .
But in other languages like C it is not so easy ..

Read actual algorithm & its implementation in C .

Insertion sort Algorithm & implementation in C

Python 2.7.6 Implementation of Insertion sort Algorithm

Algorithm is well explain in program comment

Quick sort Recursive Approch

There are many way to sort a list using quick sort concept .i.e recursive way & iterative way.

quick sort 

Recursive Approach

1. choose a no in the list a pivote
2. now sort list such that no less then pivote no. come on left of it & other on right
3. In above steps list break in two part . let left list as brand new list and repeat all steps(1,2,3).
4. do similar operation on right list as on left.

Now how to do Steps 2. there are many ways I did mention few of them..

Selection Sort (concept & algorithm)

Suppose an array A with N elements is in memory. Selection sort works as follows

First find the smallest element in the list and put it in the first position. Then, find the second smallest element in the list and put it in the second position  and so on.

Pass 1: Find the location LOC  of the smallest element in the list A[1], A[2], … A[N]. Then interchange A[LOC] and A[1]. Then: A[1] is sorted

Pass 2: Find the location LOC  of the smallest element in the sublist A[2], A[3], … A[N]. Then interchange A[LOC] and A[2]. Then: A[1],A[2]  is sorted since A[1] <= A[2].

Pass 3: Find the location LOC  of the smallest element in the sublist A[3], A[4], … A[N]. Then interchange A[LOC] and A[3]. Then: A[1], A[2],A[3]  is sorted, since A[2] <= A[3]. 

Insertion Sort (concept & algorithm)

insertion like cards

An array A with N elements A[1], A[2] … A[N] is in memory

Insertion Sort scan A from A[1] to A[N] inserting each elements A[k] into its proper position in the previously sorted subarray A[1], A[2], …. A[K-1]

Pass 1: A[1] by itself is trivially sorted

Pass 2: A[2] is inserted either before or after A[1] so that A[1], A[2] is sorted

Pass 3: A[3] is inserted in its proper place in A[1], A[2], that is before A[1], between A[1] and A[2] or after A[2] so that A[1], A[2], A[3] is sorted

Pass 4: A[4] is inserted in its proper place in A[1], A[2], A[3] so that A[1], A[2], A[3], A[4]  is sorted. 

Quick Sort (concept & algorithm )

Quick sort is an algorithm of the divide-and-conquer type

The problem of sorting a set  is reduced to the problem of sorting two smaller sets.

---

Quick Sort Approach :

Bubble Sort ( concept & algorithm )

The oldest and simplest sort in use.

Unfortunately, also the slowest.

Works by comparing each item in the list with the item next to it, and swapping them if required.

---

The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

Search & Deletion in Binary search Tree ( BST )

In previous discussion we discus about Binary search tree Now we have to do some basic operation on binary search tree.

Searching a element : it is not a tough job in BST .follow simple algorithm

>> compare root node data with require data if equal search complete otherwise if less that root node move to left else move to right child.

follow this steps for all nodes until NULL encounter it is condition for unsuccessful search.

Merge sort

Suppose the array A containing  8 elements {5, 2, 4, 7, 1, 3, 2, 6 }.
How it will be sorted see this image.

Merge Sort

download this PPT for all type of sorting : sorting.ppt

Time complexity = Q(n log n)

C program :

selection sort

It is simplest method of sorting.In this first we compare 0th element to all other element & swap values if any element found to be greater than 0th elemnt. SO after first iteration 0th elemnt is smallest no.than again choose 1st elemnt & compare it with all element come after 1st position.Than choose second..& repeat above procedure  till  (n-1)th element .
now our list is sorted..

                                                                     C code ::

Binary search

 THis method is very fast & efficient. this method require element in list be  in sorted  order.

   In this metod we compare it with element present at the center of list.IF it matches then search is    successful . Otherwise the list is divided into two halves.
                      One from 0th element to center element (first half).
                       Another from center element to last element(Second half).
 AS a result all element in first haf is smaller than center element,All element of second half are larger than cenetr element.
If  key(elemnt to be search) is smaller than center element. above procedure repeat in first half. Otherwise in second half.

C code::

Bubble sort in c

Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

C code ::