# data[].attributes.body
-Nguyễn Văn Chương(NT)
-Nguyễn Xuân Trường
-Bùi Minh Thành
-Phạm Như Hoàng

# data[].attributes.body
1/THUẬT TOÁN SẮP XẾP NHANH(QUICK SORT)
2/ THUẬT TOÁN XỬ LÝ CHUỖI( TÌM KIẾM CHUỖI)

# data[].attributes.body
cài đặt và minh họa thuật toán

# data[].attributes.body
mô tả và giải thích

# data[].attributes.body
#include<stdio.h>

void swap(int &a, int &b)

{

int t = a;

a = b;

b = t;

}

int partition (int arr[], int low, int high)

{

int pivot = arr[high];    // pivot

int left = low;

int right = high - 1;

while(true){

while(left <= right && arr[left] < pivot) left++;

while(right >= left && arr[right] > pivot) right--;

if (left >= right) break;

swap(arr[left], arr[right]);

left++;

right--;

}

swap(arr[left], arr[high]);

return left;

}

/* Hàm thực hiện giải thuật quick sort */

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

/* pi là chỉ số nơi phần tử này đã đứng đúng vị trí

và là phần tử chia mảng làm 2 mảng con trái & phải */

int pi = partition(arr, low, high);

// Gọi đệ quy sắp xếp 2 mảng con trái và phải

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

/* Hàm xuất mảng */

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

}

main()

{

int arr[] = {10, 80, 30, 90, 40, 50, 70};

int n = sizeof(arr)/sizeof(arr[0]);

quickSort(arr, 0, n-1);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

}

# data[].attributes.body
VDMH: Cho dãy số có số phần tử n=5: 10 5 7 3 1 4
Pivot= 4

Left= 0, Right=4

1  5  7  3  10  4

Left= 1, Right=3

1  3  7  5  10  4

Left= 2, Right=1

1  3  4  5  10  7

Pivot= 3

Left= 1, Right=0

1  3  4  5  10  7

Pivot= 7

Left= 4, Right=3
1  3  4  5  7  10

# data[].attributes.body
Bước 1: Lấy phần tử chốt là phần tử ở cuối danh sách.

Bước 2: Chia mảng theo phần tử chốt.

Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái.

Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải.

# data[].attributes.body
Trong phần này chúng ta có hai giai đoạn. Giai đoạn một là giai đoạn phân đoạn mảng và giai đoạn hai là giai đoạn sắp xếp .

Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.
Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.
Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
Sau khi dịch chuyển thực hiện công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.

# data[].attributes.body
Định nghĩa & nhận xét

# data[].attributes.body
QuickSort là một thuật toán Chia và Chinh phục. Nó chọn một phần tử làm trục và phân vùng mảng đã cho xung quanh trục đã chọn. Có nhiều phiên bản quickSort khác nhau chọn pivot theo những cách khác nhau.

# data[].attributes.body
Ưu điểm

Tốc độ sắp xếp nhanh.

Được sử dụng trong nhiều thư viện của các ngôn ngữ như C++, Java, ...

Nhược điểm

Phụ thuộc vào cách chọn phần tử chốt.

Không ổn định.

Nhận xét

So với sắp xếp nổi bọt thì sắp xếp nhanh mỗi lần đổi chỗ mang tính nhảy vọt. Từng lượt ta chọn một phần tử chốt, đem những số nhỏ hơn nó đặt bên trái nó, những số lớn hơn nó đặt bên phải phải. Dẫn đến số lượt đổi chỗ được ít hơn so với sự đổi chỗ từng cặp của sắp xếp nổi bọt.

# data[].attributes.body
Xử Lý Chuỗi

# data[].attributes.body
1/ So sánh chuỗi s2 với phần tử đầu chuỗi s1.
2/ Nếu không giống nhau thì dịch đến phần tử tiếp theo của chuỗi s1
3/ Đến khi đã tìm chuỗi s1 có trong chuỗi s2 thì dừng '\0'

# data[].attributes.body
#include <stdio.h>
#include <conio.h>
#include <string.h>

int findsubstr(const char *str, char *sub)
{
const char *p = str;
int len = strlen(sub);
while(*p != NULL)
{
if (strlen(p) >= len)
{
if (strncmp(p, sub, strlen(sub)) == 0)
{
return (p - str + 1);
}
}
else
{
break;
}
p++;
}
return 0;
}

main()
{
char str[] = "vncoding.net blog for developer";
char sub1[] = "blog";
printf("str = '%s'\n", str);
printf("'%s' at %d\n", sub1, findsubstr(str, sub1));
getch();
}

# data[].attributes.body
QuickSort là một thuật toán Chia và Chinh phục. Nó chọn một phần tử làm trục và phân vùng mảng đã cho xung quanh trục đã chọn. Có nhiều phiên bản quickSort khác nhau chọn pivot theo những cách khác nhau.

# data[].attributes.body
Bước 1: Lấy phần tử chốt là phần tử ở cuối danh sách.

Bước 2: Chia mảng theo phần tử chốt.

Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái.

Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải.

# data[].attributes.body
#include<stdio.h>

void swap(int &a, int &b)

{

int t = a;

a = b;

b = t;

}

int partition (int arr[], int low, int high)

{

int pivot = arr[high];    // pivot

int left = low;

int right = high - 1;

while(true){

while(left <= right && arr[left] < pivot) left++;

while(right >= left && arr[right] > pivot) right--;

if (left >= right) break;

swap(arr[left], arr[right]);

left++;

right--;

}

swap(arr[left], arr[high]);

return left;

}

/* Hàm thực hiện giải thuật quick sort */

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

/* pi là chỉ số nơi phần tử này đã đứng đúng vị trí

và là phần tử chia mảng làm 2 mảng con trái & phải */

int pi = partition(arr, low, high);

// Gọi đệ quy sắp xếp 2 mảng con trái và phải

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

/* Hàm xuất mảng */

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

}

main()

{

int arr[] = {10, 80, 30, 90, 40, 50, 70};

int n = sizeof(arr)/sizeof(arr[0]);

quickSort(arr, 0, n-1);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

}

# data[].attributes.body
Trong phần này chúng ta có hai giai đoạn. Giai đoạn một là giai đoạn phân đoạn mảng và giai đoạn hai là giai đoạn sắp xếp .

Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.
Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.
Thực hiện so sánh các phần tử với pivot. Nếu phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
Sau khi dịch chuyển thực hiện công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.

# data[].attributes.body
VDMH: Cho dãy số có số phần tử n=5: 10 5 7 3 1 4
Pivot= 4

Left= 0, Right=4

1  5  7  3  10  4

Left= 1, Right=3

1  3  7  5  10  4

Left= 2, Right=1

1  3  4  5  10  7

Pivot= 3

Left= 1, Right=0

1  3  4  5  10  7

Pivot= 7

Left= 4, Right=3
1  3  4  5  7  10

# data[].attributes.body
Ưu điểm

Tốc độ sắp xếp nhanh.

Được sử dụng trong nhiều thư viện của các ngôn ngữ như C++, Java, ...

Nhược điểm

Phụ thuộc vào cách chọn phần tử chốt.

Không ổn định.

Nhận xét

So với sắp xếp nổi bọt thì sắp xếp nhanh mỗi lần đổi chỗ mang tính nhảy vọt. Từng lượt ta chọn một phần tử chốt, đem những số nhỏ hơn nó đặt bên trái nó, những số lớn hơn nó đặt bên phải phải. Dẫn đến số lượt đổi chỗ được ít hơn so với sự đổi chỗ từng cặp của sắp xếp nổi bọt.

# data[].attributes.body
Chuỗi là một mảng một chiều mà các phần tử là các ký tự

# data[].attributes.body
Tìm một ký tự trong chuỗi

Đếm số ký tự trong chuỗi

Tìm một chuỗi con trong một chuỗi

Đảo ngược chuỗi

Tách chuỗi

# data[].attributes.body
Đầu vào: chuỗi 1 (s1), chuỗi 2 (s2)
Đầu ra: vị trí xuất hiện đầu tiên của chuỗi 2 trong chuỗi 1

# data[].attributes.body
1/ So sánh chuỗi s2 với phần tử đầu chuỗi s1.
2/ Nếu không giống nhau thì dịch đến phần tử tiếp theo của chuỗi s1
3/ Đến khi đã tìm chuỗi s1 có trong chuỗi s2 thì dừng '\0'

# data[].attributes.body
#include <stdio.h>
#include <conio.h>
#include <string.h>

int findsubstr(const char *str, char *sub)
{
const char *p = str;
int len = strlen(sub);
while(*p != NULL)
{
if (strlen(p) >= len)
{
if (strncmp(p, sub, strlen(sub)) == 0)
{
return (p - str + 1);
}
}
else
{
break;
}
p++;
}
return 0;
}

main()
{
char str[] = "vncoding.net blog for developer";
char sub1[] = "blog";
printf("str = '%s'\n", str);
printf("'%s' at %d\n", sub1, findsubstr(str, sub1));
getch();
}

# data[].attributes.body
Viết một hàm nhận ký tự cần đếm và vị trí của ký tự đó. Ví dụ countChar(String s, char c, int i)

Trong đó:

– Lặp từ 0 -> đến i-1 nếu ký tự đó đã xuất hiện thì thoát khỏi hàm (đã đếm rồi).

– Lặp từ i đến cuối chuỗi, đến số lần xuất hiện của ký tự đó

– In ký tự đó ra theo dạng c-count

Trong hàm main cho lặp từ đầu đến cuối chuỗi và gọi hàm countChar ở trên để đếm và in ra.