Showing posts with label Data structures and Algorithms. Show all posts
Showing posts with label Data structures and Algorithms. Show all posts

Monday, May 18, 2020

Java: Selection Sort


The selection sort algorithm sorts an array by repeatedly finding the minimum element
(considering ascending order) from the unsorted part and putting it at the beginning.
The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Following example explains the above steps:

arr[] = 64 25 12 22 11

Find the minimum element in arr[0...4]and place it at beginning
11 25 12 22 64

Find the minimum element in arr[1...4]and place it at beginning of arr[1...4]
11 12 25 22 64

Find the minimum element in arr[2...4] and place it at beginning of arr[2...4]
11 12 22 25 64
Find the minimum element in arr[3...4] and place it at beginning of arr[3...4]
11 12 22 25 64


public class SelectionSort {

    void sort(int arr[])
    {
        int n = arr.length;

        // One by one move boundary of unsorted subarray         
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array 
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Swap the found minimum element with the first element
                      
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
    // Prints the array     
   void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i            System.out.print(arr[i]+" ");
        System.out.println();
    }

    // Driver code to test above 
   public static void main(String args[])
    {
        SelectionSort ob = new SelectionSort();
        int arr[] = {64,25,12,22,11};
        System.out.println("input array");
        ob.printArray(arr);
        ob.sort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }
}

Sunday, May 17, 2020

Java: Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )





public class BubbleSort {
    void bubbleSort(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n-1; i++)
            for (int j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1])
                {
                    // swap arr[j+1] and arr[i] 
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
    }

    /* Prints the array */     
   void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i 
          System.out.print(arr[i] + " ");
          System.out.println();
    }

    // Driver method to test above 
    public static void main(String args[])
    {
        BubbleSort ob = new BubbleSort();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Input array");
        ob.printArray(arr);

        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }

}

Saturday, May 16, 2020

Python: Binary Search

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

class BinarySearch(object) :

    def binarySearch(self, A, K):

        # Returns index of x in arr if present, else -1 
    def binarySearch(arr, l, r, x):

       # Check base case             
       if r >= l:
                print("r,l:",r,", ",l)
                mid = round(l + (r - l) / 2)

                # If element is present at the middle itself 
                if arr[mid] == x:
                    return mid

                # If element is smaller than mid, then it can only 
                # be present in left subarray 
                elif arr[mid] ==  x:
                    print("search left side of the array: arr[mid] is ", arr[mid])
                    return binarySearch(arr, l, mid - 1, x)

                    # Else the element can only be present in right subarray                 
                else:
                    print("search right side of the array: arr[mid] is  ", arr[mid])
                    return binarySearch(arr, mid + 1, r, x)

            else:
                # Element is not present in the array 
                return -1

        result = binarySearch(A, 0, len(A)-1, K)
        return result

def main():
    x = BinarySearch()
    A = [10, 7, 8, 9, 1, 5]
    k = 1    #output = 8    #A =[7, 10, 4, 3, 20, 15]
    A.sort()
    print("array is: ",A)
    print("element ",k, " of array ", A, " is index ", x.binarySearch(A,k))

if __name__ == '__main__':
    main()