Untitled

unknown
plain_text
a month ago
27 kB
1
Indexable
Never
```## 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.

(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 *insert_at_beg(struct node *head, int data){
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
}

struct node* insert_at_end(struct node* head, int data){ //O(n)
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;

}

struct node *p = head; // to traverse the list.
}

}
//insert node after given node.
struct node *insert_after(struct node *head, int after, int data){
printf("List is Empty. \n");
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
while(p != NULL){
if(p->info == after){
}
}
printf("%d not present in List.\n", after);
}
struct node *insert_at_pos(struct node *head, int pos, int data){
if(pos < 1){
printf("position must be greater than 1");
}else if(pos == 1){
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
int cnt = 1;
if(++cnt == pos){
}
}
if(++cnt == pos){
}
printf("Cannot insert %d at position %d, As list has only %d elements.\n", data, pos, --cnt);
}
struct node *del_node(struct node *head, int data){ //O(n)
//case 1 : List is empty
printf("List is Empty\n");
}

//case 2 : deletion of head node
struct node *temp;
free(temp);
}

//case 3 : delete inbetween or end node
temp = p->link; //store the node to be deleted
free(temp);
}
}
}

// traverse of display all elements in the list
printf("List is Empty \n");
return;
}
struct node* p;
printf("List is : [ ");
while(p != NULL){
printf("%d ",p->info);
}
printf("].\n");
}
//count number of elements in list.
int cnt = 0;
struct node* p;
while(p != NULL){
cnt++;
}
return cnt;
}
// search an element in the given list.
void search(struct node* head, int data){
int pos = 1;
while(p != NULL){
if(p->info == data){
printf("Item %d found at position %d\n", data, pos);
return;
}
pos++;
}
}
//move last node to front.
}
q = p;
}
}

int main(){
int choice,data,item,pos;

printf("1.Display\n");
printf("2.Count list\n");
printf("3.Search element\n");
printf("4.Insert new node at the beginning\n");
printf("5.Insert new node at the end\n");
printf("6.Insert new node after the given node\n");
printf("7.Insert new node at the given node\n");
printf("8.Delete node\n");
printf("9.Reverse list\n");
printf("10.Quit\n\n");

scanf("%d", &choice);

while(choice != 10){

switch(choice){
case 1:
break;
case 2:
break;
case 3:
printf("Enter the data to find : ");
scanf("%d", &data);
break;
case 4:
printf("Enter the data to insert at beginning : ");
scanf("%d", &data);
break;
case 5:
printf("Enter the data to insert at end : ");
scanf("%d", &data);
break;
case 6:
printf("Insert data after node : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
break;
case 7:
printf("Insert data at node number : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
break;
case 8:
printf("Enter the data to delete : ");
scanf("%d", &data);
break;
case 9:
printf("Reversing Single Linked List is time taking. \n");
break;
case 10:
break;
default:
printf("Enter choice less than 10. \n");
}

scanf("%d", &choice);
}
return 0;
}

```

- 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). Linked list access takes O(n) time , while array takes O(1) time.
- Nodes are stored incontigously, greatly increasing the time required to access individual elements within the list, especially in case of CPU cache , As for arrays, the data is copied from RAM to CPU cache for faster access.
- Difficulties arise in linked lists when it comes to reverse traversing.

### Motivation
- Traverse list in reverse order.

### Defination.
- Doubly linked list is a LL in which we maintain two pointers head and tail. It has structure as `|prev|info|next|`.

```c
#include<stdio.h>
#include<stdlib.h>

struct node{
int info;
struct node *prev;
struct node *next;
};

struct node *insert_at_beg(struct node *head, int data){
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->prev = NULL;
}
}

struct node* insert_at_end(struct node* head, int data){ //O(n)
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->next = NULL;

}

struct node *p = head; // to traverse the list.
while(p->next != NULL){
p = p->next;
}
p->next = temp; //linking node at end
temp->prev = p;

}
//insert node after given node.
struct node *insert_after(struct node *head, int after, int data){
printf("List is Empty. \n");
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
while(p != NULL){
if(p->info == after){
temp->next = p->next;
temp->prev = p;
if(p->next != NULL)
p->next->prev = temp;
p->next = temp;

}
p = p->next;
}
printf("%d not present in List.\n", after);
}
// insert node at node number pos.
struct node *insert_at_pos(struct node *head, int pos, int data){
if(pos < 1){
printf("position must be greater than 1");
}else if(pos == 1){
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
int cnt = 1;
while(p->next != NULL){
if(++cnt == pos){
temp->next = p->next;
temp->prev = p;
if(p->next != NULL)
p->next->prev = temp;
p->next = temp;
}
p = p->next;
}
if(++cnt == pos){
temp->next = NULL;
temp->prev = p;
p->next = temp;
}
printf("Cannot insert %d at position %d, As list has only %d elements.\n", data, pos, --cnt);
}
struct node *del_node(struct node *head, int data){ //O(n)
//case 1 : List is empty
printf("List is Empty\n");
}

// case 2 : Only one element in list.
struct node *temp;
free(temp);
}
else{
}
}

//case 3 : deletion of head node
free(temp);
}

//case 4 : delete inbetween node
while(temp->next != NULL){
if(temp->info == data){
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
temp = temp->next;
}

//case 5 : delete end node
if(temp->info == data){
temp->prev->next = NULL;
free(temp);
}

}

// traverse of display all elements in the list
printf("List is Empty \n");
return;
}
struct node* p;
printf("List is : [ ");
while(p != NULL){
printf("%d ",p->info);
p = p->next;
}
printf("].\n");
}
//count number of elements in list.
int cnt = 0;
struct node* p;
while(p != NULL){
p = p->next;
cnt++;
}
return cnt;
}
// search an element in the given list.
void search(struct node* head, int data){
int pos = 1;
while(p != NULL){
if(p->info == data){
printf("Item %d found at position %d\n", data, pos);
return;
}
p=p->next;
pos++;
}
}
//move last node to front.
}
while(p->next != NULL){
p = p->next;
}
p->prev->next = NULL;
p->prev = NULL;
}
}

int main(){
int choice,data,item,pos;

printf("1.Display\n");
printf("2.Count list\n");
printf("3.Search element\n");
printf("4.Insert new node at the beginning\n");
printf("5.Insert new node at the end\n");
printf("6.Insert new node after the given node\n");
printf("7.Insert new node at the given node\n");
printf("8.Delete node\n");
printf("9.Reverse list\n");
printf("10.Quit\n\n");

scanf("%d", &choice);

while(choice != 10){

switch(choice){
case 1:
break;
case 2:
break;
case 3:
printf("Enter the data to find : ");
scanf("%d", &data);
break;
case 4:
printf("Enter the data to insert at beginning : ");
scanf("%d", &data);
break;
case 5:
printf("Enter the data to insert at end : ");
scanf("%d", &data);
break;
case 6:
printf("Insert data after node : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
break;
case 7:
printf("Insert data at node number : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
break;
case 8:
printf("Enter the data to delete : ");
scanf("%d", &data);
break;
case 9:
printf("Reversing Single Linked List is time taking. \n");
break;
case 10:
break;
default:
printf("Enter choice less than 10. \n");
}

scanf("%d", &choice);
}
return 0;
}
```

### Drawbacks
- More memory space needed, 2 pointers.
- Need to manage more number of pointer operations when perform any operation.

- After end, circle back to start. Last node points to the first node again.
- USecases : playlists, OS uses CLL for running programs.
- circular SLL & DLL
- Edge cases:
- Traversing : no NULL pointer, so p==head again after full traversal.
> Implement the CLL code yourself.

## Questions
```
1. In Insertionsort even if we use binary search to find the correct place of an element, still we have to move all elemnets to the right, so it will take O(n^2).
```

## Stack
- LIFO : Last In First Out , Last one putin will come out first.
- every object lies above or below some object.
- Eg : stack of books, stack of plates.
- stack can be implemented using arrays or linked-list.
- top is a pointer pointing to the top element of stack.

### Operations on a stack
- push : add a new element on top of the stack, and top points to it.
- pop : removes and return the top element form the stack.

### Usecases
- Expression Evaluation , Eg `x = 23 + 2 * 6 / 4 - 2` (based on precedence).
- Parenthesis check .
- Recursion call-stack.
- Many more advanced applications in computer science.

### Stack using arrays
- stores elements in contigious memory loacation.
- Sequential access available nut not need because of top pointer.
- disadvantage that once we push elements equal to maximum capacity of array, we can't push further.
### Infix to postfix
```c
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

char stack[20];
int top = -1;

void push(char ch){
stack[++top] = ch;
}
char pop(){
if(top < 0)
return ' ';
return stack[top--];
}
int priority(char ch){
if(ch == '(')
return 0;
else if(ch == '+' || ch == '-')
return 1;
else if(ch == '*' || ch == '/')
return 2;
return -1;
}

char* infix_to_postfix(char str[20]){
char* res = (char*) calloc(20, sizeof(char));
char *exp = str, temp;
int i=0;
while(*exp != '\0'){
if(isalnum(*exp))
res[i++] = *exp;
else if(*exp == '(')
push(*exp);
else if(*exp == ')'){
while((temp = pop()) != '('){
res[i++] = temp;
}
} else {
while(top > -1 && priority(stack[top]) >= priority(*exp)){
res[i++] = pop();
}
push(*exp);
}
exp++;
}
return res;
}
int main(){
char str[20] = "(2*3+4*(5-6))";
printf("%s\n", infix_to_postfix(str));

return 0;
}
```
### Infix to prefix
- Method 1:
- Reverse the intital expression string by replacing '(' with ')' and ')' with '('.
- apply postfix conversion on reversed expression string.
- reverse the obtained postfix expression to get prefix string.

### Evaluation of postfix expressions.
1. read each char of string one by one.
2. If char is an operand, push it to the stack.
3. If char is an operator, pop and store two elements from char, apply the operator on popped element, push the result onto the stack.
4. Pop result at last.
```c
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

char stack[20];
int top = -1;

void push(char ch){
stack[++top] = ch;
}
char pop(){
if(top < 0)
return ' ';
return stack[top--];
}
int priority(char ch){
if(ch == '(')
return 0;
else if(ch == '+' || ch == '-')
return 1;
else if(ch == '*' || ch == '/')
return 2;
else
return -1;
}

char* infix_to_postfix(char str[20]){
char* res = (char*) calloc(20, sizeof(char));
char *exp = str, temp;
int i=0;
while(*exp != '\0'){
if(isalnum(*exp))
res[i++] = *exp;
else if(*exp == '(')
push(*exp);
else if(*exp == ')'){
while((temp = pop()) != '('){
res[i++] = temp;
}
} else {
while(top > -1 && priority(stack[top]) >= priority(*exp)){
res[i++] = pop();
}
push(*exp);
}
exp++;
}
res[i] = '\0';
return res;
}

int int_Stack[20];
int int_top = -1;
int getdigit(char ch){
switch(ch){
case '0' : return 0;
case '1' : return 1;
case '2' : return 2;
case '3' : return 3;
case '4' : return 4;
case '5' : return 5;
case '6' : return 6;
case '7' : return 7;
case '8' : return 8;
case '9' : return 9;
default :
printf("Not valid digit.\n");
}
return -1;
}

// only for for expression having single digit operands.
int postfix_evaluation(char* postfix){
char* ptr = postfix;
while(*ptr != '\0'){
if(isalnum(*ptr)){
int_Stack[++int_top] = getdigit(*ptr);
}else{
if(int_top > 0){
int b = int_Stack[int_top--];
int a = int_Stack[int_top--];
switch(*ptr){
case '+' : int_Stack[++int_top] = a+b;
break;
case '-' : int_Stack[++int_top] = a-b;
break;
case '*' : int_Stack[++int_top] = a*b;
break;
case '/' : int_Stack[++int_top] = a/b;
break;
default :
printf("Not a valid operator.\n");
}
}
}
ptr++;
}
if(int_top == 0)
return int_Stack[int_top--];
printf("Not a valid postfix expression. \n");
return 0;
}

int main(){
char infix[20] = "(2*3+4*(5-6))";
char* postfix = infix_to_postfix(infix);
printf("Infix : %s\n", infix);
printf("Postfix : %s\n", postfix);
printf("Postfix Evaluation : %d. \n", postfix_evaluation(postfix));

return 0;
}
```
### Evaluation of prefix expressions
- similar to postfix, just traverse the expression in reverse order.

### Call-Stack
- It is also known as runtime-stack or machine-stack, and is useful for maintaining function call sequence.
- It is very useful for recursion.
- Call stack contains frame's . Each frame has several fields, which has information about calling function.

```
[fact(1) 1        ] }frame
[fact(2) 2*fact(1)] }frame      [fact(2) 2*1      ]
[fact(3) 3*fact(2)] }frame  ->  [fact(3) 3*fact(2)] -> [fact(3) 3*2      ] ->                     ->                ->120.
[fact(4) 4*fact(3)] }frame      [fact(4) 4*fact(3)]    [fact(4) 4*fact(3)]    [fact(4) 4*6      ]
[fact(5) 5*fact(4)] }frame      [fact(5) 5*fact(4)]    [fact(5) 5*fact(4)]    [fact(5) 5*fact(4)]    [fact(5) 5*24]
```
- keep track of which function called another function.
- Space complexity : O(n) // due to call stack.
- quicksort in worst case takes theta(n) space for call stack.

### sedwgick modified quicksort algorithm.
- objective : reduce worst case space complexity of quicksort from theta(n) to theta(log(n)).
```
quicksort(A, p, r):
while (p < r) // both iterative and recursive.
q = PARTITION(A, p, r);
// Recurse the smaller subarray first.
if(q - p < r - q)
quicksort(A, p, q - 1)
p = q + 1
else
quicksort(A, q + 1, r)
r = q - 1
```
- How this works :
1. reursively quicksort the smaller subarray.
2. return back to calling function, and updates the variables.
3. recursively quicksort the larger subarray.

> Left associative means perform operation from left to right. Right associative means perform operation from right to left.
> Due to slow random access of doubly linked list, only meregesort O(nLogn) or insertion sort O(n^2) can be used optimally on doubly linkws liar.

##  Print linkedlist in reverse order.
```c
return;
}
}
```

## Queues
- queues are FIFO data structures.
- First item to come in is the first to be served(out).
- Operations :
- Enqueue : Add to the queue. (Always add to the tail)
- Dequeue : Remove from the queue. (Always remove from the head)
> In Stack one pointer(top) was sufficient, in  Queue we need 2 Pointers (head and tail).

```c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
int data;
struct Node *next;
}node;

typedef struct{
node *tail;
}queue;

queue *enque(queue *qlist, int info){
node *temp = (node*) malloc(sizeof(node));
temp->data = info;
temp->next = NULL;

if(qlist->tail == NULL){
qlist->tail = temp;
}
qlist->tail->next = temp;
qlist->tail = temp;

return qlist;
}

queue *deque(queue *qlist){
printf("List is Empty. \n");
return qlist;
}
qlist->tail = NULL;
int info = temp->data;
free(temp);
return info;
}

int main(){
node node2 = {20, NULL};
node node1 = {10, &node1};
queue q, *qlist;
qlist = &q;
qlist->tail = &node2;

return 0;
}
```
```