Untitled

## Radix Sort
- we know the counting sort, radix sort is an extension of it.
- In radix sort we make use of stability of counting sort.
- Here first we sort the data on basis of unit digit of numbers and consider remaining digits of number as its satellite data.
- Then similarly we sort on basis of tenth digit data, hundredth digit data, and so on. and finally our array will be sorted at end.
```
329       720        720         329
457       355        329         355
657       436        436         436
839 ----> 457 ---->  839 ------> 457
436 (1th) 657 (10th) 355 (100th) 657
720       329        457         720
355       839        657         839
```

- Time complexity : if n is the numbers and d is the number of digits in the largest number then TC = O(n*d).

## When to use which sorting algorithm.
- Insertion Sort : use when almost sorted array. TC=O(n), SC=O(1).
- Merge Sort : array does not fit completely in RAM(external sorting). TC=O(nlog(n)), SC=O(n).
- Quick Sort : randomised QS is used as general purpose sorting algorithm. Used in C, Unix, Java.
- Counting sort : numbers between small range (0 to K).
- Radix Sort : numbers have multiple digits. 
- Bubble Sort : avoid.
---
- Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented as default sorting algorithm in python. Today it is so popular that it is used in Java SE, Android platform, GNU octave, Google Chrome.
 
### Question
Q :  if we use radix sort to sort n integers in range (n^k/2, n^k), where k is independent of n , the time taken would be?   
A : we can represent any number n with log(n) digits in binary. so n^k can be represented in klog(n) digits in binary. The TC of radix sort is O(a x n) , so TC = O(klog(n) x n) , but k is independent of n and can be treated as constant. TC = O(nlog(n)).

# Data Structures.
- A data structure is a data organization, mangement and storage format that enables efficient access and modification. More precisely a data structure is a collection of data values, the relationships among them and the functions operations that can be applied to the data.  

Eg : Arrays
- collection of elements of same datatype.
- relationship : elements are ordered in some manner, one after another.
- operations : set, get, traverse, indexing, search.

## Need of data structure
- for efficient storage, access and modification of data.
- suppose we have mapdata about cites and distance between two cities, so how can i store this data efficiently, we need a special data structure : graphs.
- every data structure has its own pros and cons. like we cant grow the size of array dynamically.

## Linked list
(Singlym Doubly, Circular)
- can overcome drawback of array.
- Linked lists can grow dynamically in size.
- Linked list consists of several nodes linked together, each node consists of a value and an address to the next node.
- In Linked list we have a head pointer which points to first node  of Linked list, and the last node of linked list points to NULL
- In Linked list the nodes are not stored at continous memory location.
- In c we implement node using structs and other language C++, Java, Python, we make use of classses.
```c
#include<stdio.h>
#include<stdlib.h>

struct node{
    int info;
    struct node* link;
};

struct node* insert_at_beg(struct node* head, int data){ //O(1)
    struct node* temp;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->info = data;
    temp->link = head;
    head = temp;
    return head; 
}
struct node* insert_at_end(struct node* head, int data){ //O(n)
    struct node *temp, *p;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->info = data; 
    temp->link = NULL;
    p=head;
    if(p){
        while(p->link != NULL){
            p=p->link; //p+=1;
        }
        p->link=temp;
    }else{
        head=temp;
    }
    return head;
}
struct node* del_node(struct node* head, int data){ //O(n)
    struct node* temp, *p;
    //empty list
    if(head=NULL)
    {
        printf("List is empty\n");
        return head;
    }
    //deletion of first node
    if(head->info==data){
        temp=head;
        head=head->link;
        free(temp);
        return head;
    }
    //deletion of inbtn or end node.
    p=head;
    while(p->link!=NULL){
        if(p->link->info == data){
            temp = p->link;
            p->link=temp->link;
            free(temp);
            return head;
        }
        p=p->link;
    }
    printf("Element %d not found\n",data);
    return head;
}
// traverse of display all elements in the list
void display(struct node* head){
    if(head==NULL){
        printf("List is Empty \n");
        return;
    }
    struct node* p;
    p=head;
    printf("List is : [ ");
    while(p!=NULL){
        printf("%d ",p->info);
        p=p->link;
    }
    printf("].\n");
}
//count number of elements in list.
int count(struct node* head){
    int cnt =0;
    struct node* p;
    p=head;
    while(p!=NULL){
        p= p->link;
        cnt++;
    }
    return cnt;
}
// search an elemetnt in the given list and return intex based on 1 indexing.
int find(struct node* head, int data){
    if(head==NULL){
        printf("List is empty.\n");
        return 0;
    }
    int cnt = 1;
    struct node* p=head;
    while(p!=NULL){
        if(p->info == data){
            return cnt;
        }
        p=p->link;
        cnt++;
    }
    return 0;
}
int main(){

}
```

### Drawbacks of Linked list
- It takes more memory than arrays because of the storage used by pointers.
- Nodes in a linked list must be read in order from the beginning (sequential access).
- Nodes are stored incontigously, greatly increasing the time required to access individual elements within the list, as in case of arrays, the data is copied from RAM to CPU cache for faster access.
- Difficulties arise in linked lists when it comes to reverse traversing.

## Doubly linked list
### Motivation
- Traverse list in reverse order.