# Untitled

unknown
plain_text
a month ago
24 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.
- circular SLL & DLL
- Edge cases:
- Traversing : no NULL pointer, so p==head again after full traversal.

## Stack
- LIFO : Last In First Out , Last one put in 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.
- maintain a pointer top to keep track of top element.

### 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.
### Infix to postfix
```c
#include<stdio.h>
#include<ctype.h>

char Stack[20]; //Global stack
int top = -1;

void push(char x){
Stack[++top] = x;
}
char pop(){
if(top < 0)
return -1;
return Stack[top--];
}
int priority(char x){
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return -1;
}
char* infixToPostfix(char* exp, char* res){
int pos = 0;
char x;
while(*exp != '\0'){
if(isalnum(*exp))  //number
*(res + pos++) = *exp;
else if(*exp == '(') //parenthesis
push(*exp);
else if(*exp == ')')
{
while(top > -1 && (x = pop()) != '('){
*(res + pos++) = x;
}
}
else
{
while(top > -1 && (priority(Stack[top]) >= priority(*exp))){
*(res + pos++) = pop();
}
push(*exp);
}
exp++;
}
while( top > -1){
*(res + pos++) = pop();
}
*(res+pos) = '\0';
return res;
};

int main(){
char exp[20] = "(2*3+4*(5-6))";
char res[20];
printf("Infix : %s .\n", exp);
printf("Postfix : %s .\n", infixToPostfix(exp,res));

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<ctype.h>

char Stack[20]; //Global stack
int top = -1;
int StackI[20];
int topI = -1;

void push(char x){
Stack[++top] = x;
}
char pop(){
if(top < 0)
return -1;
return Stack[top--];
}
void pushI(int x){
StackI[++topI] = x;
}
char popI(){
if(topI < 0)
return -1;
return StackI[topI--];
}
int priority(char x){
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return -1;
}
int charToDigit(char x){
switch (x)
{
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("Something went wrong.\n");
}
return -1;
}
int postfixEvaluation(char* exp){
topI = -1;
while(*exp != '\0'){
printf("***Iteration***\n");
printf("Expr : %s \n", exp);
if(isalnum(*exp)){
pushI(charToDigit(*exp));
printf("digit : %d\n", charToDigit(*exp));
}else{
if(topI<1){
printf("Not Enough operands to use operator %c.\n",*exp);
return 0;
}
int a = popI();
int b = popI();
switch (*exp)
{
case '+':
pushI(b+a);
break;
case '-':
pushI(b-a);
break;
case '*':
pushI(b*a);
break;
case '/':
pushI(b/a);
break;
default:
printf("%c not valid operator.\n",*exp);
return 0;
}
}
exp++;
}
if(topI!=0){
printf("Invalid Postfix expression.\n");
return 0;
}
return popI();
}
char* infixToPostfix(char* exp, char* res){
int pos = 0;
char x;
while(*exp != '\0'){
if(isalnum(*exp))  //number
*(res + pos++) = *exp;
else if(*exp == '(') //parenthesis
push(*exp);
else if(*exp == ')')
{
while(top > -1 && (x = pop()) != '('){
*(res + pos++) = x;
}
}
else
{
while(top > -1 && (priority(Stack[top]) >= priority(*exp))){
*(res + pos++) = pop();
}
push(*exp);
}
exp++;
}
while( top > -1){
*(res + pos++) = pop();
}
*(res+pos) = '\0';
return res;
};

int main(){
char exp[20] = "(2*3+4*(5-6))";
char res[20];
printf("Infix : %s .\n", exp);
printf("Postfix : %s .\n", infixToPostfix(exp,res));
printf("Evaluation of postix expression : %d", postfixEvaluation( infixToPostfix(exp,res) ));

return 0;
}
```

### 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.
-
```