What is Sorting and Searching in Data Structure

Sorting means arranging a set of data in some order. There are different methods that are used to sort the data in ascending order or descending order .

We will develop following techquinic for sorting

1.)    Bubble sorting

2.)     Insertion Sort

3.)     Selection Sort

4.)     Quick sort

5.)     Shell sort

6.)     Merge sort

1.) BUBBLE SORT

It is very simple sorting technique Thus this technique is not efficient to other techniques. Suppose we sort the element in descending order. The bubble sort loops through the elements in the list comparing the adjacent element and moves the largest element to the top of the list.

 Write an algorithm for bubble sort

Here n represent number of element in list

Bubble sort(n, list)

Step:1  [Initialize the variable  ]

              I =1

Step:2  [Repeat through step 5 ]

              While(I<n)

Step:3    J=1

Step:4  Repeat through step 5 while (j<n-i)

Step:5  if(list[J]<list[J+1])

              I ) TEMP =list[J]

              II) list[J+1]=list[J]

             III) list[J] =TEMP

Step:6         Exit

2.) SELECTON SORT

The selection sort starts from  element and searches the entire list until it find the minimum value. The sort palace the minimum value in the first place.select the second element and searches for the smallest  element. The process  continuous until the complete the list.

Here list represent list of element and size re[present size of element

Write an algorithm of selection sort

Step:1   [Initially]

               Current=0;

Step:2   [repeat through step:7]

              While(current<size)

 Step:3     J=current+1

Step:4   [Repeat through step 6]

              While(j<size)

  Step:5  if(list[current>=list[J])

I)                 temp=list[current]

II)               list[current]=list[J]

III)              list[J] = temp

 step:6   J=J+1

 step: 7  current=current+1

step:8  exit

3 .)  INSERTION SORT

         One of the simplest method to sort an array is an insertion sort. Simple tech when you insert element add in sorted form.

Write an algorithm of insertion sort

 Here list represent  list of element and N represent number of element in list

 Step:1  [Initialize]

               list[0]=0

Step:2 [Repeat through step 3 to 5 ]           

                While(I<N)

  Step:3  I) temp=list[I]

              II) pointer = I-1

Step: 4 while(temp<list[pointer])

I)       list[pointer+1] =list[pointer]

II)     pointer=pointer-1

step:5 list[pointer] = temp

step: 6 exit

4.)    SHELL SORT

 The shell sort technique work by comparing the list element that are separated   by a specific distance.

Write an algorithm of shell sort

 Here   List represents the list of element  and size represent the size of the list

Step: 1 [ Initialize]

            dist =size/2

step:2  [Repeat through step 6 ]

             while (dist=dist/2)

 step:3 swap =0

 step:4  [Repeat through step 6]

                  while(swap)  

 step:5 [ Repeat through step 6 ]

            For I=0  to I< (size-dis)

  Step :6  if(list[I]>list[I+dist])

I)       temp=list[I]

II)     list[I]=list[I+dist]           

III)    list[I+dist]=temp

IV)    swap=1

[End of for loop]

 Step:7  [display element in sorted order]

                   For I=0 to I<size

                Output(list[I])

                      End loop

Step ;8  Exit

5.)    QUICK SORT

                      Quick sort treats an array as a list of elements. when sort begins it selects the list’s middle element as pivot. The sort then divides the list into two sub lists one with elements that are less than the list pivot and a second list with elements greater than or equal to the list pivot.

The sort then recursively invokes itself with both lists. Each time when the sort is invoked, it further divides the elements into smaller sub –lists.

Write an algorithm of Quick Sort

Here list is represent list of elements, First is represent the  position of first element in the list, and last represent  and last represent last element of list.

First and Last variable change at execution time of function.

Start

Step:1  [Initially value and find middle poison of list]

              Low = First

              High = Last

              Pivot=list[(low+high)/2]

Step:2  [Repeat through step 7 ]

                   While(low<=high)

Step :3  [Repeat  step 4 ]

                   While(list[low]<pivot)

    Step: 4   low = low+1

    Step:5   Repeat step 6 while(list[high] >pivot)

Step :6  high =high -1

Step :7  If(low<=high)

I)            temp =list[low]

II)           list[low]=list [high]

III)         list[high]= temp

IV)         low=low+1

V)           high =high-1

step:8     If(Fisrt<high)            

                 Q_sort(list,First,high)

Step:9   If (low<last)

                    Q_sort(list,low,las)

Step:10  Exit

SEARCHING   TECHNIQUE

Computer system are often used to store large amounts of data from which individual records can be retrieved according to some search technique so the efficient storage of the data to facilities fast searching is an important issue.

 

 There are two type of searching technique

1.)    LINEAR SEARCHE

2.)     BINARY SEARCHE

LINEAR SERCHE

This is simplest technique to find out an element in an unsorted list. Suppose, we have an unsorted  list which contain n elements  and want to search the value of a particular elements  for that we have to check each elements one by one and find at any passion.

Write an algorithm for linear search of elements.

Start

Step : 1 [Initailly]

              Count =0

Step :2  [check each elements repeat step 3 ]

               For I=0 to I<size

Step :3  [check for elements ]

               If(list[I]==num)

                  Count=1

                End if

                End loop

Step: 4   [result find]

                If(count==1)

          Print(“element is found”)

           Else

            Print(“element is not found”)

Step:5  Exit